Equitable coloring of planar graphs with maximum degree at least eight

Alexandr Kostochka; Duo Lin; Zimu Xiang

doi:10.1016/j.disc.2024.113964

Equitable coloring of planar graphs with maximum degree at least eight

Alexandr Kostochka, Duo Lin, Zimu Xiang

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree Δ≥3 that is not the complete graph K_Δ+1 or the complete bipartite graph K_Δ,Δ admits an equitable coloring with Δ colors. For planar graphs, the conjecture has been confirmed for Δ≥13 by Yap and Zhang and for 9≤Δ≤12 by Nakprasit. In this paper, we present a proof that confirms the conjecture for graphs embeddable into a surface with non-negative Euler characteristic with maximum degree Δ≥9 and for planar graphs with maximum degree Δ≥8.

Original language	English (US)
Article number	113964
Journal	Discrete Mathematics
Volume	347
Issue number	6
DOIs	https://doi.org/10.1016/j.disc.2024.113964
State	Published - Jun 2024

Keywords

Equitable coloring
Planar graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2024.113964

Library availability

Discover UIUC Full Text

Cite this

@article{92f6ae7c6b914cdeb10125364c37ebcb,

title = "Equitable coloring of planar graphs with maximum degree at least eight",

abstract = "The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree Δ≥3 that is not the complete graph KΔ+1 or the complete bipartite graph KΔ,Δ admits an equitable coloring with Δ colors. For planar graphs, the conjecture has been confirmed for Δ≥13 by Yap and Zhang and for 9≤Δ≤12 by Nakprasit. In this paper, we present a proof that confirms the conjecture for graphs embeddable into a surface with non-negative Euler characteristic with maximum degree Δ≥9 and for planar graphs with maximum degree Δ≥8.",

keywords = "Equitable coloring, Planar graphs",

author = "Alexandr Kostochka and Duo Lin and Zimu Xiang",

note = "Publisher Copyright: {\textcopyright} 2024 The Author(s)",

year = "2024",

month = jun,

doi = "10.1016/j.disc.2024.113964",

language = "English (US)",

volume = "347",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Equitable coloring of planar graphs with maximum degree at least eight

AU - Kostochka, Alexandr

AU - Lin, Duo

AU - Xiang, Zimu

PY - 2024/6

Y1 - 2024/6

N2 - The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree Δ≥3 that is not the complete graph KΔ+1 or the complete bipartite graph KΔ,Δ admits an equitable coloring with Δ colors. For planar graphs, the conjecture has been confirmed for Δ≥13 by Yap and Zhang and for 9≤Δ≤12 by Nakprasit. In this paper, we present a proof that confirms the conjecture for graphs embeddable into a surface with non-negative Euler characteristic with maximum degree Δ≥9 and for planar graphs with maximum degree Δ≥8.

AB - The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree Δ≥3 that is not the complete graph KΔ+1 or the complete bipartite graph KΔ,Δ admits an equitable coloring with Δ colors. For planar graphs, the conjecture has been confirmed for Δ≥13 by Yap and Zhang and for 9≤Δ≤12 by Nakprasit. In this paper, we present a proof that confirms the conjecture for graphs embeddable into a surface with non-negative Euler characteristic with maximum degree Δ≥9 and for planar graphs with maximum degree Δ≥8.

KW - Equitable coloring

KW - Planar graphs

UR - http://www.scopus.com/inward/record.url?scp=85187682967&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85187682967&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2024.113964

DO - 10.1016/j.disc.2024.113964

M3 - Article

AN - SCOPUS:85187682967

SN - 0012-365X

VL - 347

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 6

M1 - 113964

ER -

Equitable coloring of planar graphs with maximum degree at least eight

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this