2
$\begingroup$

Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.

Kelman claims that this conjecture is equivalent to a stronger one, which imposes some restrictions on the Hamiltonian cycles. The statement of this equivalence lies in his paper, "Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles", AMS Translations, Series 2 158, pp. 127–140.

It is Theorem 17 in this paper.

Unfortunately, Kelmans does not even give a sketch of the proof. I have read in detail the paper, but was not able to reconstruct the proof.

So I would like to know if :

1) these details are written somewhere.

2) is it true that if a Barnette graph is Hamiltonian, then Kelman's conditions can be imposed on that very graph (without any more assumption).

Thank you.

$\endgroup$
1
  • $\begingroup$ Ok, I got it. Kelmans' idea is to use a hypothetical counterexample to the strong conjecture as a building block to construct a (huge) counterexample to the usual Barnette conjecture. Hence his work does not give a positive answer to Question 2). Question 2) remains interesting to me. $\endgroup$ Jun 26, 2013 at 14:13

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.