We construct an infinite family of counterexamples to Thomassen’s conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red such that the blue subgraph has maximum degree at most 1 and the red subgraph minimum degree at least 1 and contains no path on 4 vertices.
Bibliografisk noteFunding Information:
The research was initiated at the Structural graph theory workshop at Gułtowy, 24-28 June 2019 sponsored by ERC Starting Grant “CUTACOMBS Cuts and decompositions: algorithms and combinatorial properties”, grant agreement No 714704. The first author is supported by the Danish research council under grant number DFF-7014-00037B. The second author was supported by the grant no. 19-04113Y of the Czech Science Foundation (GAČR) and the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004). The third author was supported by the Danish Council for Independent Research, Natural Sciences, grant DFF-8021-00249, AlgoGraph.
© 2021, The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature.