On Barnette's conjecture

Abstract: A conjecture of Barnette states that every 3-connected cubic bipartite plane graph has a Hamilton cycle, which is equivalent to the statement that every simple even plane triangulation admits a partition of its vertex set into two subsets so that each induces a tree. Let

G

be a simple even plane triangulation and suppose that

V_{1}, V_{2}, V_{3}

is a 3-coloring of the vertex set of

G

. Let

B_{i}

,

i = 1, 2, 3

, be the set of all vertices in

V_{i}

of the degree at least 6. We prove that if induced graphs

G [B_{1} c u p B_{2}]

and

G [B_{1} c u p B_{3}]

are acyclic, then the following properties are satisfied: [6pt] (1) For every path

a b c

there is possible to partition the vertex set of

G

into two subsets so that each induces a tree, and one of them contains the edge

a b

and avoids the vertex

c

, [6pt] (2) For every path

a b c

with vertices

a

,

c

of the same color there is possible to partition the vertex set of

G

into two subsets so that each induces a tree, and one of them contains the path

a b c

.

Recommendations

Cites work

Cited in

(24)

This page was built for publication: On Barnette's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q968428)