کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648485 | 1632429 | 2011 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A note on Barnette’s conjecture A note on Barnette’s conjecture](/preview/png/4648485.png)
A well-known conjecture of Barnette states that every 3-connected cubic bipartite planar graph has a Hamiltonian cycle, which is equivalent to the statement that every 3-connected even plane triangulation admits a 2-tree coloring, meaning that the vertices of the graph have a 2-coloring such that each color class induces a tree. In this paper we present a new approach to Barnette’s conjecture by using 2-tree coloring.A Barnette triangulation is a 3-connected even plane triangulation, and a B-graph is a smallest Barnette triangulation without a 2-tree coloring. A configuration is reducible if it cannot be a configuration of a B-graph. We prove that certain configurations are reducible. We also define extendable, non-extendable and compatible graphs; and discuss their connection with Barnette’s conjecture.
Journal: Discrete Mathematics - Volume 311, Issues 23–24, 28 December 2011, Pages 2711–2715