Graph coloring satisfying restraints

DOI10.1016/0012-365X(90)90113-VMaRDI QIDQ910410zbMATH OpenOpenAlexWikidataFDO

Authors N. E. Zubov

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(90)90113-v

zbMATH Keywords

amenable graphproper k-restraintstrongly critical graphsvertex colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

For an integer \(k\geq 2\), a proper k-restraint on a graph G is defined to be a function from the vertex set of G to a set \(\{\) 1,2,...,k\(\}\) of k colours. A proper k-colouring c of G (i.e. a vertex colouring with the property that adjacent vertices receive different of the k colours) satisfies the restraint r if c(v)\(\neq r(v)\) for each vertex v of G. A graph G is said to be amenably k-colourable if for each non-constant proper k-restraint on G there is a k-colouring of G satisfying this restraint. A graph with the chromatic number k being amenably k- colourable is called an amenable graph. In this paper infinite families of amenable graphs are constructed. Classical methods for constructing new critical graphs are used to find new amenable graphs from given ones (join operation, Hajós construction). Examples of non-amenable critical graphs whose join with a single vertex is amenable are given. The concept of strongly critical graphs defined in this paper plays an essential role in constructing amenable graphs.

Recommendations

• Amenable colorings
• Classifying coloring graphs
• Extremal restraints for graph colourings
• Restraints permitting the largest number of colourings
• On color critical graphs with large adaptable chromatic numbers

Cites work

• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• Colour-critical graphs and hypergraphs
• Graph-theoretic parameters concerning domination, independence, and irredundance
• scientific article; zbMATH DE number 3361909 (Why is no real title available?)
• On critical subgraphs of colour-critical graphs
• Paths and Circuits in Critical Graphs
• Subgraphs of colour-critical graphs

Cited in

(6)

• Restraints permitting the largest number of colourings
• Strategic Coloring of a Graph
• Coloring Graphs with Constraints on Connectivity
• Extremal restraints for graph colourings
• A broken cycle theorem for the restrained chromatic function
• Amenable colorings

This page was built for publication: Graph coloring satisfying restraints

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