Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
11017679 | European Journal of Combinatorics | 2019 | 10 Pages |
Abstract
We discuss conjectures on Hamiltonicity in cubic graphs (Tait, Barnette, Tutte), on the dichromatic number of planar oriented graphs (Neumann-Lara), and on even graphs in digraphs whose contraction is strongly connected (Hochstättler). We show that all of them fit into the same framework related to cuts in matchings. This allows us to find a counterexample to the conjecture of Hochstättler and show that the conjecture of Neumann-Lara holds for all planar graphs on at most 26 vertices. Finally, we state a new conjecture on bipartite cubic oriented graphs, that naturally arises in this setting.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kolja Knauer, Petru Valicov,