On the Structure of Hamiltonian Graphs with Small Independence Number
<|reference_start|>On the Structure of Hamiltonian Graphs with Small Independence Number: A Hamiltonian path (cycle) in a graph is a path (cycle, respectively) which passes through all of its vertices. The problems of deciding the existence of a Hamiltonian cycle (path) in an input graph are well known to be NP-complete, and restricted classes of graphs which allow for their polynomial-time solutions are intensively investigated. Until very recently the complexity was open even for graphs of independence number at most 3. So far unpublished result of Jedli\v{c}kov\'{a} and Kratochv\'{\i}l [arXiv:2309.09228] shows that for every integer $k$, Hamiltonian path and cycle are polynomial-time solvable in graphs of independence number bounded by $k$. As a companion structural result, we determine explicit obstacles for the existence of a Hamiltonian path for small values of $k$, namely for graphs of independence number 2, 3, and 4. Identifying these obstacles in an input graph yields alternative polynomial-time algorithms for Hamiltonian path and cycle with no large hidden multiplicative constants.<|reference_end|>
@article{jedličková2024on,
    title={On the Structure of Hamiltonian Graphs with Small Independence Number},
    author={Nikola Jedliv{c}kov'a, Jan Kratochv'il},
    journal={arXiv preprint arXiv:2403.03668},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.03668},
    primaryClass={math.CO cs.CC}
}