×

Graph coloring satisfying restraints. (English) Zbl 0696.05024

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.
Reviewer: U.Baumann

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bollobás, B., Graph Theory, An Introductory Course (1979), Springer: Springer New York · Zbl 0418.05049
[2] Descartes, B., Solution of Problem 4526, Amer. Math. Monthly, 61, 352-353 (1954)
[3] Dirac, G. A., A theorem of R.L. Brooks and a conjecture of H. Hadwiger, Proc. London Math. Soc., 7, 3, 161-195 (1957) · Zbl 0077.17002
[4] Kelly, J. B.; Kelly, L. M., Paths and circuits in critical graphs, Amer. J. Math., 76, 786-792 (1954) · Zbl 0056.16902
[5] Lovász, L., Coverings and colorings of hypergraphs, (Proceedings of the fourth Southwestern Conference on Combinatorics, Graph Theory and Computing (1973), Utilitas Mathematica Publishing: Utilitas Mathematica Publishing Winnipeg), 3-12
[6] Stiebitz, M., Subgraphs of colour-critical graphs, Combinatorica, 7, 3, 303-312 (1987) · Zbl 0642.05020
[7] Toft, B., On the maximal number of edges of critical \(k\)-chromatic graphs, Studia Sci. Math. Hungar., 5, 461-470 (1970) · Zbl 0228.05111
[8] Toft, B., Color-critical graphs and hypergraphs, J. Combinat. Theory, 16, 145-161 (1974), (Ser. B) · Zbl 0269.05117
[9] Toft, B., On critical subgraphs of colour-critical graphs, Discrete Math., 7, 377-392 (1974) · Zbl 0271.05112
[10] B. Toft, Personal communication.; B. Toft, Personal communication.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.