<p>Acyclic graph coloring problems have applications in network design, graph algorithms, and combinatorial optimization. Given two simple, connected, and undirected graphs, <i>G</i> and <i>H</i>, their corona product <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(G {\circ } H\)</EquationSource> </InlineEquation> provides a way to combine the structures of <i>G</i> and <i>H</i> while introducing additional interconnections between their vertex sets <i>V</i>(<i>G</i>) and <i>V</i>(<i>H</i>). In this research, the acyclic coloring parameters of <i>G</i> and <i>H</i>, <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi _{a}(G)\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi _{a}(H)\)</EquationSource> </InlineEquation>, respectively, are analyzed by considering the color classes of <i>V</i>(<i>G</i>) and <i>V</i>(<i>H</i>) in three different cases to find <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">\( \chi _{a}(G {\circ } H)\)</EquationSource> </InlineEquation>, the acyclic coloring of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(G {\circ } H\)</EquationSource> </InlineEquation>. This research also analyzes <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">\( \chi _{a}(G {\circ } H)\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">\( \chi _{a}(H {\circ } G)\)</EquationSource> </InlineEquation> based on <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi _{a}(G)\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi _{a}(H)\)</EquationSource> </InlineEquation>. This research proves the important result that the maximum degree of <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(G {\circ } H\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="153" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta (G {\circ } H) = \chi '_{a}(G {\circ } H)\)</EquationSource> </InlineEquation>, the acyclic chromatic index of <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40009_2025_1801_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(G {\circ } H\)</EquationSource> </InlineEquation>, when <i>G</i> and <i>H</i> satisfy the acyclic edge coloring conjecture.</p>

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

Acyclic Graph Coloring Analysis in the Corona Product of Graphs

  • V. Vinitha Navis,
  • Raja Marappan

摘要

Acyclic graph coloring problems have applications in network design, graph algorithms, and combinatorial optimization. Given two simple, connected, and undirected graphs, G and H, their corona product \(G {\circ } H\) provides a way to combine the structures of G and H while introducing additional interconnections between their vertex sets V(G) and V(H). In this research, the acyclic coloring parameters of G and H, \(\chi _{a}(G)\) and \(\chi _{a}(H)\) , respectively, are analyzed by considering the color classes of V(G) and V(H) in three different cases to find \( \chi _{a}(G {\circ } H)\) , the acyclic coloring of \(G {\circ } H\) . This research also analyzes \( \chi _{a}(G {\circ } H)\) and \( \chi _{a}(H {\circ } G)\) based on \(\chi _{a}(G)\) and \(\chi _{a}(H)\) . This research proves the important result that the maximum degree of \(G {\circ } H\) , \(\Delta (G {\circ } H) = \chi '_{a}(G {\circ } H)\) , the acyclic chromatic index of \(G {\circ } H\) , when G and H satisfy the acyclic edge coloring conjecture.