Graphs that contain a K_1,2,3 and no induced subdivision of K₄ are 4-colorable

2023/05/06 by Rong Chen, Chen, Rong
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2305.03889

openalex publication_date 2023/05/06 · openalex created_date 2023/05/10 · openalex updated_date 2026/07/28

Abstract

In 2012, Lévêque, Maffray, and Trotignon conjectured that each graph G that contains no induced subdivision of K₄ is 4-colorable. In this paper, we prove that this conjecture holds when G contains a K_1,2,3.

Related

• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• (1,0,0)-colorability of planar graphs without cycles of length 4 or 6
• Coloring graphs with no induced subdivision of K₄⁺
• A relaxation of Steinberg's Conjecture
• Graphs without a 3-connected subgraph are 4-colorable