Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen (Q2685314)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen |
scientific article; zbMATH DE number 7655632
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen |
scientific article; zbMATH DE number 7655632 |
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