<p>For simple graphs <i>G</i> and <i>H</i>, the Hom complex <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41468_2025_219_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="84" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{Hom}(G,H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>Hom</mtext> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is a polyhedral complex whose vertices are the graph homomorphisms <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41468_2025_219_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="59" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\rightarrow H\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo stretchy="false">→</mo> <mi>H</mi> </mrow> </math></EquationSource> </InlineEquation> and whose edges connect the pairs of homomorphisms which differ in a single vertex of <i>G</i>. Hom complexes play an important role in an algebro-topological approach to the graph coloring problem. It is known that <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41468_2025_219_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="84" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{Hom}(G,H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>Hom</mtext> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is homotopy equivalent to a disjoint union of points and circles when both <i>G</i> and <i>H</i> are cycles. We generalize this known result by showing that the same holds whenever <i>G</i> is connected and <i>H</i> is a cycle. To this end, we explicitly construct the universal cover of each connected component of <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="41468_2025_219_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="84" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{Hom}(G,H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>Hom</mtext> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and prove that it is contractible. Additionally, we provide a simple criterion to determine whether the connected component containing a given homomorphism is homotopy equivalent to a point or circle.</p>

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

Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles

  • Soichiro Fujii,
  • Yuni Iwamasa,
  • Kei Kimura,
  • Yuta Nozaki,
  • Akira Suzuki

摘要

For simple graphs G and H, the Hom complex \(\textrm{Hom}(G,H)\) Hom ( G , H ) is a polyhedral complex whose vertices are the graph homomorphisms \(G\rightarrow H\) G H and whose edges connect the pairs of homomorphisms which differ in a single vertex of G. Hom complexes play an important role in an algebro-topological approach to the graph coloring problem. It is known that \(\textrm{Hom}(G,H)\) Hom ( G , H ) is homotopy equivalent to a disjoint union of points and circles when both G and H are cycles. We generalize this known result by showing that the same holds whenever G is connected and H is a cycle. To this end, we explicitly construct the universal cover of each connected component of \(\textrm{Hom}(G,H)\) Hom ( G , H ) and prove that it is contractible. Additionally, we provide a simple criterion to determine whether the connected component containing a given homomorphism is homotopy equivalent to a point or circle.