<p>A <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lambda\)</EquationSource> </InlineEquation><i>-vertex coloring</i> of a graph <i>G</i> is an assignment of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lambda\)</EquationSource> </InlineEquation> colors to the vertices of <i>G</i> such that adjacent vertices have different colors. We say that two <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lambda\)</EquationSource> </InlineEquation>-vertex colorings <i>f</i> and <i>g</i> of <i>G</i> are called <i>distinct</i> if there exists a vertex assigned different colors. The <i>chromatic polynomial</i> of <i>G</i> on variable <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lambda\)</EquationSource> </InlineEquation>, denoted by <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi (G;\lambda )\)</EquationSource> </InlineEquation>, is the number of <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lambda\)</EquationSource> </InlineEquation>-vertex colorings of <i>G</i>. The cartesian product of two simple graphs <i>G</i> and <i>H</i> is the graph <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq9.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(G \square H\)</EquationSource> </InlineEquation>, whose vertex set is <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="103" /> </InlineMediaObject> <EquationSource Format="TEX">\(V(G) \times V(H)\)</EquationSource> </InlineEquation> and whose edge set consists of all pairs <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="102" /> </InlineMediaObject> <EquationSource Format="TEX">\((u_1,v_1)(u_2,v_2)\)</EquationSource> </InlineEquation> such that either <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="94" /> </InlineMediaObject> <EquationSource Format="TEX">\(u_1u_2 \in E(G)\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq13.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\(v_1 = v_2\)</EquationSource> </InlineEquation>, or <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq14.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="93" /> </InlineMediaObject> <EquationSource Format="TEX">\(v_1v_2 \in E(H)\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq15.gif" Format="GIF" Height="12" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">\(u_1 = u_2\)</EquationSource> </InlineEquation>. In 2008, Pfaff and Walker determined the chromatic polynomial of <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="53" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_3 \square P_n\)</EquationSource> </InlineEquation> using the edge deletion-contraction theorem. However, this result is a recursive expression in two variables, making its computation extremely costly for large <i>n</i>. In 2024, Yadav et al. applied the transfer matrix method to compute the chromatic polynomials of <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq17.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_m \square P_n\)</EquationSource> </InlineEquation> for <InlineEquation ID="IEq18"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq18.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="45" /> </InlineMediaObject> <EquationSource Format="TEX">\(n \in \mathbb {N}\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq19"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq19.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="97" /> </InlineMediaObject> <EquationSource Format="TEX">\(m \in \{1,2,3\}\)</EquationSource> </InlineEquation>. In this paper, we determine a closed-form formula for the chromatic polynomial of <InlineEquation ID="IEq20"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="53" /> </InlineMediaObject> <EquationSource Format="TEX">\(C_3 \square P_n\)</EquationSource> </InlineEquation> such that <i>n</i> is a positive integer, given by <InlineEquation ID="IEq21"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq21.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="110" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi (C_3 \square P_n; \lambda ) =\)</EquationSource> </InlineEquation><InlineEquation ID="IEq22"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="44425_2025_15_Article_IEq22.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="297" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lambda (\lambda -1)(\lambda -2) (\lambda ^3 - 6 \lambda ^2 + 14 \lambda - 13)^{n - 1}.\)</EquationSource> </InlineEquation>&#xa0;&#xa0;</p>

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

The Chromatic Polynomial of \(C_3 \square P_n\)

  • Mayara Christina,
  • Mauro Nigro,
  • Diana Sasaki

摘要

A \(\lambda\) -vertex coloring of a graph G is an assignment of \(\lambda\) colors to the vertices of G such that adjacent vertices have different colors. We say that two \(\lambda\) -vertex colorings f and g of G are called distinct if there exists a vertex assigned different colors. The chromatic polynomial of G on variable \(\lambda\) , denoted by \(\chi (G;\lambda )\) , is the number of \(\lambda\) -vertex colorings of G. The cartesian product of two simple graphs G and H is the graph \(G \square H\) , whose vertex set is \(V(G) \times V(H)\) and whose edge set consists of all pairs \((u_1,v_1)(u_2,v_2)\) such that either \(u_1u_2 \in E(G)\) and \(v_1 = v_2\) , or \(v_1v_2 \in E(H)\) and \(u_1 = u_2\) . In 2008, Pfaff and Walker determined the chromatic polynomial of \(C_3 \square P_n\) using the edge deletion-contraction theorem. However, this result is a recursive expression in two variables, making its computation extremely costly for large n. In 2024, Yadav et al. applied the transfer matrix method to compute the chromatic polynomials of \(P_m \square P_n\) for \(n \in \mathbb {N}\) and \(m \in \{1,2,3\}\) . In this paper, we determine a closed-form formula for the chromatic polynomial of \(C_3 \square P_n\) such that n is a positive integer, given by \(\chi (C_3 \square P_n; \lambda ) =\) \(\lambda (\lambda -1)(\lambda -2) (\lambda ^3 - 6 \lambda ^2 + 14 \lambda - 13)^{n - 1}.\)