Scholarlink

<p>A graph <i>G</i> is edge-<i>k</i>-choosable if, for any assignment of lists <i>L</i>(<i>e</i>)of at least <i>k</i> colors to all edges <i>e</i> ∈ <i>E</i>(<i>G</i>), there exists a proper edge coloring such that the color of <i>e</i> belongs to <i>L</i>(<i>e</i>) for all <i>e</i> ∈ <i>E</i>(<i>G</i>). 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 <i>C</i><sub>7</sub> (so, without chords), thereby extending a result due to Dong, Liu and Li.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2025年1月24日

查看全文
  • Li Zhang,
  • Hajo Broersma,
  • You Lu,
  • Shenggui Zhang

摘要

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.