Equitable coloring of interval graphs and products of graphs

2009/03/08 by Bor-Liang Chen, Chen, Bor-Liang, Ko‐Wei Lih +3 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.0903.1396

Abstract

We confirm the equitable Δ-coloring conjecture for interval graphs and establish the monotonicity of equitable colorability for them. We further obtain results on equitable colorability about square (or Cartesian) and cross (or direct) products of graphs.

Cited by

• A step toward Chen-Lih-Wu conjecture
• Equitable chromatic threshold of Kronecker products of complete graphs
• Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs
• Equitable chromatic threshold of complete multipartite graphs

Related

• Results and Problems on Equitable Coloring of Graphs
• Equitable coloring of Kronecker products of complete multipartite graphs and complete graphs
• Complexity of tree-coloring interval graphs equitably
• Equitable Colorings of Corona Multiproducts of Graphs
• Equitable coloring of graphs beyond planarity