List Edge Colorings of Planar Graphs without Non-induced 7-cycles

  • Li Zhang
  • , Hajo Broersma*
  • , You Lu
  • , Shenggui Zhang
  • *Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

7 Downloads (Pure)

Abstract

A graph G is edge-k-choosable if, for any assignment of lists L(e)of at least k colors to all edges e ∈ E(G), there exists a proper edge coloring such that the color of e belongs to L(e) for all e ∈ E(G). One of Vizing’s classic conjectures asserts that every graph is edge-(Δ + 1)-choosable. It is known since 1999 that this conjecture is true for general graphs with Δ ≤ 4. More recently, in 2015, Bonamy confirmed the conjecture for planar graph with Δ ≥ 8, but the conjecture is still open for planar graphs with 5 ≤ Δ ≤ 7. We confirm the conjecture for planar graphs with Δ ≥ 6 in which every 7-cycle (if any) induces a C7 (so, without chords), thereby extending a result due to Dong, Liu and Li.

Original languageEnglish
Pages (from-to)1037-1054
Number of pages18
JournalActa Mathematica Sinica (English Series)
Volume41
Issue number3
Early online date24 Jan 2025
DOIs
Publication statusPublished - Mar 2025

Keywords

  • 2025 OA procedure
  • 05B25
  • 20B25
  • Combinatorial Nullstellensatz
  • discharging
  • edge-k-choosability
  • list edge coloring
  • Planar graph
  • 05B05

Fingerprint

Dive into the research topics of 'List Edge Colorings of Planar Graphs without Non-induced 7-cycles'. Together they form a unique fingerprint.

Cite this