@book{bf5c90e03b1248ed8ae9df30e050a05b,

title = "A note on a conjecture concerning tree-partitioning 3-regular graphs",

abstract = "If $G$ is a 4-connected maximal planar graph, then $G$ is Hamiltonian (by a theorem of Whitney), implying that its dual graph $G^*$ is a cyclically 4-edge connected 3-regular planar graph admitting a partition of the vertex set into two parts, each inducing a tree in $G^*$, a so-called tree-partition. It is a natural question whether each cyclically 4-edge connected 3-regular graph admits such a tree-partition. This was conjectured by Jaeger, and recently independently by the first author. The main result of this note shows that each connected 3-regular graph on $n$ vertices admits a partition of the vertex set into two sets such that precisely $n/2+2$ edges have end vertices in each set. This is a necessary condition for having a tree-partition. We also show that not all cyclically 3-edge connected 3-regular (planar) graphs admit a tree-partition, and present the smallest counterexamples.",

keywords = "MSC-05C35, MSC-05C38, IR-30611, EWI-3247, METIS-141252, MSC-05C45",

author = "T. Bohme and T. Bohme and Broersma, {Haitze J.} and Hilde Tuinstra",

note = "Imported from MEMORANDA",

year = "1998",

language = "Undefined",

isbn = "0169-2690",

series = "Memorandum / University of Twente, Faculty of Applied Mathematics, ISSN 0921-1969 ; no. 1427",

publisher = "Universiteit Twente",

}