Abstract
We survey some parity arguments and problems in graph theory, in
particular some that can be attacked using the cycle space of a
graph. We discuss some results on specific collections of
cyclesthat generate the cycle space. We explain how thespace
generated by the cycles through two prescribed edges in a graph is
used in a proof of the conjecturemade by B. Toft in 1974 that
every $4$-chromatic graph contains atotally odd $K_4$-subdivision,
that is, a subdivision of $K_4$ in which each edge of $K_4$
corresponds to an odd path. (Another proof of Toft's conjecture
was found independently by W. Zang). We prove the new result that
every $4$-connected graph with at least three triangles contains a
totally odd $K_4$-subdivision if and only if it does notcontain a
vertex whose deletion results in a bipartite graph.In particular,
every $4$-connected planar graph contains a totally odd
$K_4$-subdivision. Finally, we offer some conjectures on path
systems and subdivisions with parity constraints on the lengths.
Original language | English |
---|---|
Journal | London Mathematical Society Lecture Notes |
Volume | 267 |
Pages (from-to) | 223-237 |
Publication status | Published - 1999 |