Equitable coloring planar graphs with large girth

DOI10.1016/J.DISC.2007.08.059MaRDI QIDQ2470470zbMATH OpenOpenAlexFDO

Authors Ping Wang, Jian-Liang Wu

Publication date 14 February 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.08.059

zbMATH Keywords

equitable coloringgirthouterplanar graphsplanar graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

An equitable coloring of a graph \(G\) is a proper vertex coloring such that the difference in size of every two color classes is at most one. The equitable threshold \(\chi_{\text{Eq}}^\ast(G)\) is the smallest integer \(m\) such that \(G\) has an equitable coloring using \(n\) colors for every \(n \geq m\). It is proved in this paper that \(\chi_{\text{Eq}}^\ast(G)=\chi(G)\) if \(G\) is a non-bipartite planar graph with girth at least 26 and minimum degree at least 2, or \(G\) is a 2-connected outerplanar graph with girth at least 4.

Recommendations

• Equitable coloring of sparse planar graphs
• Equitable colorings of planar graphs without short cycles
• Equitable coloring of planar graphs without 4,5,6-cycles
• Equitable coloring of planar graphs without 4-and 5-cycles
• Equitable list colorings of planar graphs without short cycles

Cites work

• A list analogue of equitable coloring
• Equitable and proportional coloring of trees
• Equitable Coloring
• Equitable coloring and the maximum degree
• Equitable coloring of trees
• Equitable colorings of outerplanar graphs
• Graph Colorings
• Graph theory
• scientific article; zbMATH DE number 1302199 (Why is no real title available?)
• scientific article; zbMATH DE number 1308943 (Why is no real title available?)
• scientific article; zbMATH DE number 1046311 (Why is no real title available?)
• scientific article; zbMATH DE number 2079370 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• On Equitable Coloring of d-Degenerate Graphs
• On equitable coloring of bipartite graphs

Cited in

(12)

• Equitable coloring and equitable choosability of graphs with small maximum average degree
• Relaxed equitable colorings of planar graphs with girth at least 8
• On the equitable edge-coloring of 1-planar graphs and planar graphs
• Equitable coloring of sparse planar graphs
• Equitable and list equitable colorings of planar graphs without 4-cycles
• Equitable vertex arboricity of graphs
• Equitable cluster partition of planar graphs with girth at least 12
• Equitable list coloring of sparse graphs
• Equitable and list equitable colorings of planar graphs without 5-cycles
• The equitable non-split domination number of graphs
• Equitable cluster partition of graphs with small maximum average degree
• Equitable defective coloring of sparse planar graphs

This page was built for publication: Equitable coloring planar graphs with large girth

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