- FR
- EN
lundi 26 Novembre, 14h, salle D 102
Abstract :
In the 19th century Tait conjectured that every planar cubic 3-connected graph is Hamiltonian. If true, it would have solved the Four Color Problem. On the other hand a conjecture of Neumann-Lara asserts that every planar oriented graph can be vertex-partitioned into two acyclic sets. This can be seen as a directed version of Tait’s Hamiltonicity Conjecture. In this talk we will explain how these conjectures together with other similar questions fit in the same framework related to cuts in matchings. We will show then a construction of a 3-edge connected oriented graph satisfying the property that for every even subgraph E, the graph obtained by contracting the edges of E is not strongly connected. This disproves a recent conjecture of Hochstättler. At the end we will provide experimental evidence for Neumann-Lara’s conjecture and discuss on tools that might be helpful to search for counterexamples.
The talk is based on joint work with Kolja Knauer.
Preprint and article are available on :
https://www.sciencedirect.com/science/article/pii/S0195669818301574
https://arxiv.org/pdf/1712.06143.pdf
