Equitable Colorings of Planar Graphs without Short Cycles

Details Equitable Colorings of Planar Graphs without Short Cycles Equitable Colorings of Planar Graphs without Short Cycles

2012-03-02

arxiv.org/abs/1203.0379v1

Mathematics

Combinatorics

Scientific paper

An \emph{equitable coloring} of a graph is a proper vertex coloring such that the sizes of every two color classes differ by at most 1. Chen, Lih, and Wu conjectured that every connected graph $G$ with maximum degree $\Delta \geq 2$ has an equitable coloring with $\Delta$ colors, except when $G$ is a complete graph or an odd cycle or $\Delta$ is odd and $G=K_{\Delta,\Delta}.$ Nakprasit proved the conjecture holds for planar graphs with maximum degree at least 9. Zhu and Bu proved that the conjecture holds for every $C_3$-free planar graph with maximum degree at least 8 and for every planar graph without $C_4$ and $C_5$ with maximum degree at least 7. In this paper, we prove that the conjecture holds for planar graphs in various settings, especially for every $C_3$-free planar graph with maximum degree at least 6 and for every planar graph without $C_4$ with maximum degree at least 7, which improve or generalize results on equitable coloring by Zhu and Bu. Moreover, we prove that the conjecture holds for every planar graph of girth at least 6 with maximum degree at least 5.

Affiliated with

Also associated with

No associations

Rating

Equitable Colorings of Planar Graphs without Short Cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Equitable Colorings of Planar Graphs without Short Cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Equitable Colorings of Planar Graphs without Short Cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-165971