Premium
Every graph occurs as an induced subgraph of some hypohamiltonian graph
Author(s) -
Zamfirescu Carol T.,
Zamfirescu Tudor I.
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22228
Subject(s) - combinatorics , mathematics , bipartite graph , graph , outerplanar graph , planar graph , statement (logic) , discrete mathematics , line graph , pathwidth , law , political science
We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for K 3 , and Collier and Schmeichel, who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph.