<p>Let <i>G</i> be a connected plane graph that can have loops and multiple edges. An <i>l</i>-facial edge-coloring of a plane graph <i>G</i> is a coloring of edges of <i>G</i> such that any two edges, that share the same facial trail of length at most <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2904_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="35" /> </InlineMediaObject> <EquationSource Format="TEX">\(l + 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>l</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, receive distinct colors. It is an edge variant of the <i>l</i>-facial vertex coloring, which arose as a generalization of the well-known cyclic coloring. It was conjectured by Lužar et al. in 2015 that every plane graph admits an <i>l</i>-facial edge-coloring with at most <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2904_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(3l + 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>3</mn> <mi>l</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> colors for any <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2904_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">\(l \ge 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>l</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. It is known that the bound <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2904_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(3l+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>3</mn> <mi>l</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> is tight for general plane graphs. The conjecture was recently confirmed for <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2904_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">\(l \le 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>l</mi> <mo>≤</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> by Horňák, Lužar and Štorgel (3-facial edge-coloring of plane graphs, Discrete Math. 346 (2023) 113312). In this note we prove that the conjecture holds, in the case when <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2904_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">\(l \ge 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>l</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>, for every graph whose reduction (the graph obtained from <i>G</i> by suppressing all its 2-vertices) is 3-edge connected, and the length of the longest path in <i>G</i> with interior vertices of degree 2 is at most <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2904_Article_IEq7.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="TEX">\(\frac{3l + 1}{10}\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mrow> <mn>3</mn> <mi>l</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>10</mn> </mfrac> </math></EquationSource> </InlineEquation>.</p>

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

A Note on the Facial Edge-Coloring Conjecture

  • Stanislav Jendrol’,
  • Alfréd Onderko

摘要

Let G be a connected plane graph that can have loops and multiple edges. An l-facial edge-coloring of a plane graph G is a coloring of edges of G such that any two edges, that share the same facial trail of length at most \(l + 1\) l + 1 , receive distinct colors. It is an edge variant of the l-facial vertex coloring, which arose as a generalization of the well-known cyclic coloring. It was conjectured by Lužar et al. in 2015 that every plane graph admits an l-facial edge-coloring with at most \(3l + 1\) 3 l + 1 colors for any \(l \ge 1\) l 1 . It is known that the bound \(3l+1\) 3 l + 1 is tight for general plane graphs. The conjecture was recently confirmed for \(l \le 3\) l 3 by Horňák, Lužar and Štorgel (3-facial edge-coloring of plane graphs, Discrete Math. 346 (2023) 113312). In this note we prove that the conjecture holds, in the case when \(l \ge 4\) l 4 , for every graph whose reduction (the graph obtained from G by suppressing all its 2-vertices) is 3-edge connected, and the length of the longest path in G with interior vertices of degree 2 is at most \(\frac{3l + 1}{10}\) 3 l + 1 10 .