Equitable colorings of planar graphs without short cycles

DOI10.1016/J.TCS.2012.09.014MaRDI QIDQ1929237zbMATH OpenOpenAlexFDO

Authors Kittikorn Nakprasit, Keaitsuda Nakprasit

Publication date 7 January 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

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

cycle equitable coloring girth planar graph

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

Abstract: 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

D e l t a g e q 2

has an equitable coloring with

D e l t a

colors, except when

G

is a complete graph or an odd cycle or

D e l t a

is odd and

G = K_{D e l t a, D e l t a} .

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.

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Equitable colorings of planar graphs without short cycles

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