A note on Barnette's conjecture
Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c |V(G) | vertices.
Vorschau
Zitieren
Rechte
Nutzung und Vervielfältigung:
