<p>Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2949_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi \)</EquationSource> </InlineEquation> be a proper edge-coloring of a graph <i>G</i>. An edge <i>e</i> is <i>rich</i> if all the edges adjacent to <i>e</i> receive distinct colors. Note that, if every non-isolated edge is rich, then the coloring <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2949_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi \)</EquationSource> </InlineEquation> is a strong edge-coloring, where every color class is an induced matching. Petruševski and Škrekovski (Discrete Math. 347:113803, 2024) introduced the concept of rich-neighbor edge-coloring as a weakening of strong edge-coloring. A proper <i>k</i>-edge-coloring <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2949_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi \)</EquationSource> </InlineEquation> is a <i>rich</i>-<i>neighbor</i> <i>k</i>-<i>coloring</i> if each non-isolated edge is adjacent to at least one rich edge. Petruševski and Škrekovski (Discrete Math. 347:113803, 2024) conjectured that every connected subcubic graph admits a rich-neighbor 5-coloring except for <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2949_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_4\)</EquationSource> </InlineEquation>. In this paper, we show that if <i>G</i> is a subcubic graph with no adjacent 3-vertices, then <i>G</i> has a rich-neighbor 5-coloring.</p>

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

On the Rich-Neighbor Edge-Colorings of Subcubic Graphs

  • Lily Chen,
  • Yi Tan,
  • Xiangqian Zhou

摘要

Let \(\phi \) be a proper edge-coloring of a graph G. An edge e is rich if all the edges adjacent to e receive distinct colors. Note that, if every non-isolated edge is rich, then the coloring \(\phi \) is a strong edge-coloring, where every color class is an induced matching. Petruševski and Škrekovski (Discrete Math. 347:113803, 2024) introduced the concept of rich-neighbor edge-coloring as a weakening of strong edge-coloring. A proper k-edge-coloring \(\phi \) is a rich-neighbor k-coloring if each non-isolated edge is adjacent to at least one rich edge. Petruševski and Škrekovski (Discrete Math. 347:113803, 2024) conjectured that every connected subcubic graph admits a rich-neighbor 5-coloring except for \(K_4\) . In this paper, we show that if G is a subcubic graph with no adjacent 3-vertices, then G has a rich-neighbor 5-coloring.