Equitable coloring of sparse planar graphs

DOI10.1137/090751803MaRDI QIDQ3013148zbMATH OpenOpenAlexFDO

Authors Rong Luo, Jean-Sébastien Sereni, D. Christopher Stephens, Gexin Yu

Publication date 18 July 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.06031

zbMATH Keywords

equitable coloringgirthplanar graphs

Mathematics Subject Classification ID

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

Abstract: A proper vertex coloring of a graph $G$ is equitable if the sizes of color classes differ by at most one. The equitable chromatic threshold $ch{i}_{eq}^{\ast }(G)$ of $G$ is the smallest integer $m$ such that $G$ is equitably $n$-colorable for all $ngem$. We show that for planar graphs $G$ with minimum degree at least two, $ch{i}_{eq}^{\ast }(G)le4$ if the girth of $G$ is at least $10$, and $ch{i}_{eq}^{\ast }(G)le3$ if the girth of $G$ is at least $14$.

Recommendations

• Equitable coloring planar graphs with large girth
• Equitable coloring of planar graphs without 4,5,6-cycles
• Equitable colorings of planar graphs without short cycles
• On equitable colorings of sparse graphs
• Equitable coloring of planar graphs without 4-and 5-cycles

Cited in

(12)

• Equitable cluster partition of graphs with small maximum average degree
• Equitable cluster partition of planar graphs with girth at least 12
• On the equitable edge-coloring of 1-planar graphs and planar graphs
• On equitable colorings of sparse graphs
• Equitable coloring planar graphs with large girth
• Equitable coloring and equitable choosability of graphs with small maximum average degree
• Equitable list coloring of sparse graphs
• Equitable colorings of planar graphs with maximum degree at least nine
• Equitable defective coloring of sparse planar graphs
• Equitable and list equitable colorings of planar graphs without 5-cycles
• Relaxed equitable colorings of planar graphs with girth at least 8
• A generalization of Grötzsch Theorem on the local-equitable coloring

This page was built for publication: Equitable coloring of sparse planar graphs

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