A star edge coloring is a proper edge coloring where the induced subgraph of any two color classes has no paths or cycles with four edges. The smallest number of colors used among all star edge colorings of a graph G,  denoted by <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi '_s(G),$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mi>s</mi> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> is the star chromatic index. For an outerplanar graph O with <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">$\varDelta (O)\ge 3,$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>Δ</mi> <mo stretchy="false">(</mo> <mi>O</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>3</mn> <mo>,</mo> </mrow> </math></EquationSource> </InlineEquation> Bezegová et al. gave a conjecture: <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi '_s(O)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mi>s</mi> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>O</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is no more than <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="111" /> </InlineMediaObject> <EquationSource Format="TEX">$ \lfloor 1.5\varDelta (O)\rfloor +1.$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>⌊</mo> <mn>1.5</mn> <mi>Δ</mi> <mo stretchy="false">(</mo> <mi>O</mi> <mo stretchy="false">)</mo> <mo>⌋</mo> <mo>+</mo> <mn>1</mn> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation> Dvořák et al. conjectured that <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi '_s(H')\le 6$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mi>s</mi> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <msup> <mi>H</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation> for any subcubic graph <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq6.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">$H'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>H</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation>. It is known that only three subcubic graphs H with <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="77" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi '_s(H)=6$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mi>s</mi> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation>. In this paper, an infinite sequence of cubic graphs G with <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="145" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi '_s(G)=ch'_s(G)=6$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mi>s</mi> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>c</mi> <msubsup> <mi>h</mi> <mi>s</mi> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mn>6</mn> </mrow> </math></EquationSource> </InlineEquation> is constructed. For striped maximal outerplanar graph SO, we have <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1875_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="158" /> </InlineMediaObject> <EquationSource Format="TEX">$\chi '_s(SO)\le \varDelta (SO) +8$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>χ</mi> <mi>s</mi> <mo>′</mo> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mi>O</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi>Δ</mi> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mi>O</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mn>8</mn> </mrow> </math></EquationSource> </InlineEquation>.

Star Edge Coloring of Outerplanar and Cubic Graphs: Bounds and Constructions

期刊论文
发表日期：

2025年5月6日

查看全文

Xingchao Deng,
Yan Liu,
Xinge Feng

摘要

A star edge coloring is a proper edge coloring where the induced subgraph of any two color classes has no paths or cycles with four edges. The smallest number of colors used among all star edge colorings of a graph G, denoted by $\chi '_s(G),$ $χ_{s}^{'} (G),$ is the star chromatic index. For an outerplanar graph O with $\varDelta (O)\ge 3,$ $Δ (O) \geq 3,$ Bezegová et al. gave a conjecture: $\chi '_s(O)$ $χ_{s}^{'} (O)$ is no more than $ \lfloor 1.5\varDelta (O)\rfloor +1.$ $⌊ 1.5 Δ (O) ⌋ + 1 .$ Dvořák et al. conjectured that $\chi '_s(H')\le 6$ $χ_{s}^{'} (H^{'}) \leq 6$ for any subcubic graph $H'$ $H^{'}$ . It is known that only three subcubic graphs H with $\chi '_s(H)=6$ $χ_{s}^{'} (H) = 6$ . In this paper, an infinite sequence of cubic graphs G with $\chi '_s(G)=ch'_s(G)=6$ $χ_{s}^{'} (G) = c h_{s}^{'} (G) = 6$ is constructed. For striped maximal outerplanar graph SO, we have $\chi '_s(SO)\le \varDelta (SO) +8$ $χ_{s}^{'} (S O) \leq Δ (S O) + 8$ .