A 3-connected cubic planar bipartite graph is Hamiltonian, i.e., Barnette’s conjecture. When all the faces of graph are coloured with one colour and its adjacent side by the other colour then conjecture holds. While considering a cubic planar graph which is not a bipartite graph then the graph formed in which the colour on a face is blue will be arbitrary. The graph thus formed as a result by contacting the vertex along with a face on the graph and the graph formed at last should contain quasi spanning tree face. A polynomial time algorithm is used based on tree parity for even degree. When the resultant graph has a non-crossing Euler tour use polynomial time algorithm should have degree 8. When the conjecture is false, the Hamiltonian is NP-complete
Volume 11 | 12-Special Issue
Pages: 505-512
DOI: 10.5373/JARDCS/V11SP12/20193245