A closure for Hamilton-connectedness in $\{K_{1,3},Γ_3\}$-free graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916335833841664 |
|---|---|
| author | Kabela, Adam Ryjáček, Zdeněk Skyvová, Mária Vrána, Petr |
| author_facet | Kabela, Adam Ryjáček, Zdeněk Skyvová, Mária Vrána, Petr |
| contents | We introduce a closure technique for Hamilton-connectedness of $\{K_{1,3},Γ_3\}$-free graphs, where $Γ_3$ is the graph obtained by joining two vertex-disjoint triangles with a path of length $3$. The closure turns a claw-free graph into a line graph of a multigraph while preserving its (non)-Hamilton-connectedness. The most technical parts of the proof are computer-assisted.
The main application of the closure is given in a subsequent paper showing that every $3$-connected $\{K_{1,3},Γ_3\}$-free graph is Hamilton-connected, thus resolving one of the two last open cases in the characterization of pairs of connected forbidden subgraphs implying Hamilton-connectedness. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03036 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A closure for Hamilton-connectedness in $\{K_{1,3},Γ_3\}$-free graphs Kabela, Adam Ryjáček, Zdeněk Skyvová, Mária Vrána, Petr Combinatorics We introduce a closure technique for Hamilton-connectedness of $\{K_{1,3},Γ_3\}$-free graphs, where $Γ_3$ is the graph obtained by joining two vertex-disjoint triangles with a path of length $3$. The closure turns a claw-free graph into a line graph of a multigraph while preserving its (non)-Hamilton-connectedness. The most technical parts of the proof are computer-assisted. The main application of the closure is given in a subsequent paper showing that every $3$-connected $\{K_{1,3},Γ_3\}$-free graph is Hamilton-connected, thus resolving one of the two last open cases in the characterization of pairs of connected forbidden subgraphs implying Hamilton-connectedness. |
| title | A closure for Hamilton-connectedness in $\{K_{1,3},Γ_3\}$-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.03036 |