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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references