<p>A <i>locally irregular decomposition</i> of a graph <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation> is a collection <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="101" /> </InlineMediaObject> <EquationSource Format="TEX">\(\{ G_1, \ldots ,G_k \}\)</EquationSource> </InlineEquation> of edge-disjoint subgraphs of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation> such that <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="212" /> </InlineMediaObject> <EquationSource Format="TEX">\(E(G_1) \cup \cdots \cup E(G_k) = E(G)\)</EquationSource> </InlineEquation> and every <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(G_i\)</EquationSource> </InlineEquation> is <i>locally irregular</i>, i.e., <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq6.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="111" /> </InlineMediaObject> <EquationSource Format="TEX">\(d_{G_i}(u) \ne d_{G_i}(v)\)</EquationSource> </InlineEquation> for every edge <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="85" /> </InlineMediaObject> <EquationSource Format="TEX">\(uv \in E(G_i)\)</EquationSource> </InlineEquation>. The smallest <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq8.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\)</EquationSource> </InlineEquation> for which <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation> has a locally irregular decomposition of size <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq8.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\)</EquationSource> </InlineEquation> is called the <i>irregular chromatic index</i> of <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation>, and is denoted by <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi '_{\textrm{irr}}(G)\)</EquationSource> </InlineEquation>. A <i>blow-up</i> of a graph <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq13.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(H\)</EquationSource> </InlineEquation> with <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq14.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="153" /> </InlineMediaObject> <EquationSource Format="TEX">\(V(H) = \{ v_1, \ldots ,v_h \}\)</EquationSource> </InlineEquation> is a graph <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation> obtained by replacing each vertex <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq16.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(v_i\)</EquationSource> </InlineEquation> of <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq13.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="19" /> </InlineMediaObject> <EquationSource Format="TEX">\(H\)</EquationSource> </InlineEquation> with an independent set <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq18.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(V_i\)</EquationSource> </InlineEquation>, and each edge <InlineEquation ID="IEq19"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq19.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="29" /> </InlineMediaObject> <EquationSource Format="TEX">\(v_iv_j\)</EquationSource> </InlineEquation> with all edges between <InlineEquation ID="IEq20"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq18.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(V_i\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq21"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq21.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(V_j\)</EquationSource> </InlineEquation>. We prove that, for any cycle <InlineEquation ID="IEq22"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq22.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_k\)</EquationSource> </InlineEquation> of length <InlineEquation ID="IEq23"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq23.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \ge 3\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq24"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq24.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="82" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi '_{\textrm{irr}}(G) \le 2\)</EquationSource> </InlineEquation> for any blow-up <InlineEquation ID="IEq25"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="18" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\)</EquationSource> </InlineEquation> of <InlineEquation ID="IEq26"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_27_Article_IEq22.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_k\)</EquationSource> </InlineEquation> with at least one class of size greater than 1.</p>

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

On the Irregular Chromatic Index of Blow-Ups of Cycles

  • Pedro S. M. Arraes,
  • Carla N. Lintzmayer,
  • Guilherme O. Mota,
  • Maycon Sambinelli

摘要

A locally irregular decomposition of a graph \(G\) is a collection \(\{ G_1, \ldots ,G_k \}\) of edge-disjoint subgraphs of \(G\) such that \(E(G_1) \cup \cdots \cup E(G_k) = E(G)\) and every \(G_i\) is locally irregular, i.e., \(d_{G_i}(u) \ne d_{G_i}(v)\) for every edge \(uv \in E(G_i)\) . The smallest \(k\) for which \(G\) has a locally irregular decomposition of size \(k\) is called the irregular chromatic index of \(G\) , and is denoted by \(\chi '_{\textrm{irr}}(G)\) . A blow-up of a graph \(H\) with \(V(H) = \{ v_1, \ldots ,v_h \}\) is a graph \(G\) obtained by replacing each vertex \(v_i\) of \(H\) with an independent set \(V_i\) , and each edge \(v_iv_j\) with all edges between \(V_i\) and \(V_j\) . We prove that, for any cycle \(C_k\) of length \(k \ge 3\) , \(\chi '_{\textrm{irr}}(G) \le 2\) for any blow-up \(G\) of \(C_k\) with at least one class of size greater than 1.