zbMATH — the first resource for mathematics

Conditional colorability in graphs. (English) Zbl 0556.05027
Graphs and applications, Proc. 1st Symp. Graph theory, Boulder/Colo. 1982, 127-136 (1985).
[For the entire collection see Zbl 0547.00012.]
Author’s abstract: ”One of the most important invariants of a graph is its chromatic number and this interest has not been diminished by the computer-assisted proof of the Four Color Theorem. The chromatic number \(\chi\) (G) has been generalized in several different directions. We propose a formulation which integrates these various approaches. This general concept, called conditional colorability, associates a prescribed graph theoretic property P with the parts of a partition of the vertex set V or the edge set E of the graph G. Then the conditional chromatic number (or the conditional chromatic index) of G with respect to P is the minimum number of parts in such a partition of V (or of E). The aspects of the chromatic number of G to be considered from the viewpoint of conditional colorability include the chromatic polynomial, critical graphs, the achromatic number, and associated questions in topological graph theory.”
Reviewer: S.Stahl

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory