Every $3$-connected $\{K_{1,3},Î_3\}$-free graph is Hamilton-connected

Adam Kabela; ZdenÄk RyjÃ¡Äek; MÃ¡ria SkyvovÃ¡; Petr VrÃ¡na

paper

Every $3$ -connected ${K_{1, 3}, I^_{3}}$ -free graph is Hamilton-connected

arXiv:2410.18309

Abstract

We show that every $3$ -connected ${K_{1, 3}, I^_{3}}$ -free graph is Hamilton-connected, where $I^_{3}$ is the graph obtained by joining two vertex-disjoint triangles with a path of length $3$ . This resolves one of the two last open cases in the characterization of pairs of connected forbidden subgraphs implying Hamilton-connectedness. The proof is based on a new closure technique, developed in a previous paper, and on a structural analysis of small subgraphs, cycles and paths in line graphs of multigraphs. The most technical steps of the analysis are computer-assisted. Keywords: Hamilton-connected; closure; forbidden subgraph; claw-free; $I^_{3}$ -free

arXiv admin note: text overlap with arXiv:2406.03036

Every 3-connected {K1,3​,I^3​}-free graph is Hamilton-connected

Abstract

Every $3$ -connected ${K_{1, 3}, I^_{3}}$ -free graph is Hamilton-connected