Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.19144 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910009172951040 |
|---|---|
| author | Matsushita, Takahiro |
| author_facet | Matsushita, Takahiro |
| contents | The Hom complex $\mathrm{Hom}(G, H)$ of graphs is a simplicial complex associated to a pair of graphs $G$ and $H$, and its homotopy type is of interest in the graph coloring problem and the homomorphism reconfiguration problem. In this paper, we show that if $G$ is a connected graph and $H$ is a square-free connected graph, then every connected component of $\mathrm{Hom}(G, H)$ is homotopy equivalent to a point, a circle, $H$ or a connected double cover over $H$. We also obtain a certain relation between the fundamental group of $\mathrm{Hom}(G,H)$ and realizable walks studied in the homomorphism reconfiguration problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_19144 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hom complexes of graphs whose codomains are square-free Matsushita, Takahiro Combinatorics Algebraic Topology The Hom complex $\mathrm{Hom}(G, H)$ of graphs is a simplicial complex associated to a pair of graphs $G$ and $H$, and its homotopy type is of interest in the graph coloring problem and the homomorphism reconfiguration problem. In this paper, we show that if $G$ is a connected graph and $H$ is a square-free connected graph, then every connected component of $\mathrm{Hom}(G, H)$ is homotopy equivalent to a point, a circle, $H$ or a connected double cover over $H$. We also obtain a certain relation between the fundamental group of $\mathrm{Hom}(G,H)$ and realizable walks studied in the homomorphism reconfiguration problem. |
| title | Hom complexes of graphs whose codomains are square-free |
| topic | Combinatorics Algebraic Topology |
| url | https://arxiv.org/abs/2412.19144 |