If the vertices of a graph G are colored with k colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then G is said to be equitably k-colorable. The equitable chromatic number \(\chi _{_{=}}(G)\) is the smallest integer k such that G is equitably k-colorable. The introductory section surveys results on the equitable chromatic number obtained before 1990. Research on equitable coloring gained significant attention starting from the early 1990s. Subsequent sections provide positive evidence for the important equitable Δ-coloring conjecture, drawing from various graph classes including forests, split graphs, outerplanar graphs, series-parallel graphs, planar graphs, graphs with low degeneracies, graphs with bounded treewidth, Kneser graphs, interval graphs, and others. The investigation extends to three types of graph products and a list version for equitable coloring. The wider context of graph packing is explored in relation to equitable coloring, followed by a study of conjectures for equitable Δ-coloring of disconnected graphs. Variants of the well-known Hajnal and Szemerédi theorem are discussed, leading to a brief summary of applications of equitable coloring. Related concepts such as equitable edge-coloring, equitable total-coloring, and equitable defective coloring are also introduced and examined. This chapter is an update of Lih (Equitable coloring of graphs. In Handbook of Combinatorial Optimization, ed. by P.M. Pardalos, D.-Z. Du, R.L. Graham, vol. 2, 2nd edn. (Springer, New York, 2013) pp. 1199–1248.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Equitable Coloring of Graphs

  • Ko-Wei Lih

摘要

If the vertices of a graph G are colored with k colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then G is said to be equitably k-colorable. The equitable chromatic number \(\chi _{_{=}}(G)\) is the smallest integer k such that G is equitably k-colorable. The introductory section surveys results on the equitable chromatic number obtained before 1990. Research on equitable coloring gained significant attention starting from the early 1990s. Subsequent sections provide positive evidence for the important equitable Δ-coloring conjecture, drawing from various graph classes including forests, split graphs, outerplanar graphs, series-parallel graphs, planar graphs, graphs with low degeneracies, graphs with bounded treewidth, Kneser graphs, interval graphs, and others. The investigation extends to three types of graph products and a list version for equitable coloring. The wider context of graph packing is explored in relation to equitable coloring, followed by a study of conjectures for equitable Δ-coloring of disconnected graphs. Variants of the well-known Hajnal and Szemerédi theorem are discussed, leading to a brief summary of applications of equitable coloring. Related concepts such as equitable edge-coloring, equitable total-coloring, and equitable defective coloring are also introduced and examined. This chapter is an update of Lih (Equitable coloring of graphs. In Handbook of Combinatorial Optimization, ed. by P.M. Pardalos, D.-Z. Du, R.L. Graham, vol. 2, 2nd edn. (Springer, New York, 2013) pp. 1199–1248.