Extremal restraints for graph colourings

MaRDI QIDQ5500320zbMATH OpenFDO

Authors Aysel Erey, Jian Li, Jason I. Brown

Publication date 5 August 2015

Full work available at URL https://arxiv.org/abs/1611.08920

zbMATH Keywords

chromatic polynomialgraph colouringrestrained chromatic polynomialrestraint

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: A {em restraint} on a (finite undirected) graph $G=(V,E)$ is a function $r$ on $V$ such that $r(v)$ is a finite subset of $mathbbN$; a proper vertex colouring $c$ of $G$ is {em permitted} by $r$ if $c(v)otinr(v)$ for all vertices $v$ of $G$ (we think of $r(v)$ as the set of colours {em forbidden} at $v$). Given a large number of colors, for restraints $r$ with exactly one colour forbidden at each vertex the smallest number of colorings is permitted when $r$ is a constant function, but the problem of what restraints permit the largest number of colourings is more difficult. We determine such extremal restraints for complete graphs and trees.

Recommendations

• Restraints permitting the largest number of colourings
• Graph coloring satisfying restraints
• A broken cycle theorem for the restrained chromatic function
• scientific article; zbMATH DE number 446487
• Some results concerning the complexity of restricted colorings of graphs

Cited in

(7)

• Restraints permitting the largest number of colourings
• Maximum number of colourings: 5-chromatic case
• scientific article; zbMATH DE number 1047736 (Why is no real title available?)
• The Typical Structure of Gallai Colorings and Their Extremal Graphs
• A broken cycle theorem for the restrained chromatic function
• Maximum number of colourings: 4-chromatic graphs
• Graph coloring satisfying restraints

This page was built for publication: Extremal restraints for graph colourings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5500320)