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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom