Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen (Q2685314)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen |
scientific article |
Statements
Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen (English)
0 references
21 February 2023
0 references
\textit{C. Thomassen} [J. Comb. Theory, Ser. B 128, 192--218 (2018; Zbl 1375.05110)] conjectured that: Every 3-connected cubic graph has a red-blue vertex coloring such that the blue subgraph has a maximum degree of at most 1 and the red subgraph has a minimum degree of at least 1 and contains no 3-edge path. In [\textit{T. Bellitto} et al., Graphs Comb. 37, No. 6, 2595--2599 (2021; Zbl 1479.05295)] is constructed an infinite family of graphs refuting the above conjecture, but still leaving the question open for some important graph classes. In this paper the authors prove that the conjecture is true for 2-connected outerplanar graphs, subdivisions of \(K_4\), and 1-subdivisions of cubic graphs. Also, they show that the conjecture is true for every genuine subdivision of any subcubic multigraph, where a genuine subdivision is a subdivision such that every edge is subdivided at least once, and conjectured that Thomasssen's conjecture is true for every \(K_4\)-minor-free graph.
0 references
graph colorings
0 references
subcubic graphs
0 references
Wegner's conjecture
0 references
outerplanar graphs
0 references
subdivisions of graphs
0 references