Cover Image

Graphs without a 3-connected subgraph are 4-colorable

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bonnet, Édouard, Feghali, Carl, Nguyen, Tung, Scott, Alex, Seymour, Paul, Thomassé, Stéphan, Trotignon, Nicolas
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Discrete Mathematics 05C15, 05C40 G.2.2
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Every Graph is Essential to Large Treewidth
by: Alecu, Bogdan, et al.
Published: (2025)

Unavoidable induced subgraphs in graphs with complete bipartite induced minors
by: Chudnovsky, Maria, et al.
Published: (2024)

Dichromatic Number and Cycle Inversions
by: Charbit, Pierre, et al.
Published: (2024)

(Even hole, triangle)-free graphs revisited
by: Martins, Beatriz, et al.
Published: (2026)

Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
by: Bonnet, Édouard, et al.
Published: (2023)

Sparse Induced Subgraphs of Large Treewidth
by: Bonnet, Édouard
Published: (2024)

Lollipops, dense cycles and chords
by: Dvořák, Zdeněk, et al.
Published: (2025)

First Order Logic and Twin-Width in Tournaments and Dense Oriented Graphs
by: Geniet, Colin, et al.
Published: (2022)

Excluding a Forest Induced Minor
by: Bonnet, Édouard, et al.
Published: (2025)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

On treewidth and maximum cliques
by: Chudnovsky, Maria, et al.
Published: (2024)

Symmetric-Difference (Degeneracy) and Signed Tree Models
by: Bonnet, Édouard, et al.
Published: (2024)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
by: Bonnet, Édouard, et al.
Published: (2023)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
by: Bonnet, Édouard, et al.
Published: (2024)

An Overview of Universal Obstructions for Graph Parameters
by: Paul, Christophe, et al.
Published: (2023)

Recognizing Relating Edges in Graphs without Cycles of Length 6
by: Levit, Vadim E., et al.
Published: (2024)

Optimal List Recoloring of Subcubic Graphs and Complete Multipartite Graphs
by: De Meyer, Lucas
Published: (2025)

Coloring Graphs With No Totally Odd Clique Immersion
by: McFarland, Caleb
Published: (2025)

Gallai's Path Decomposition for 2-degenerate Graphs
by: Anto, Nevil, et al.
Published: (2022)

Secure Total Domination Number in Maximal Outerplanar Graphs
by: Aita, Yasufumi, et al.
Published: (2024)

A Lower bound for Secure Domination Number of an Outerplanar Graph
by: Araki, Toru
Published: (2024)

On the Boxicity of Line Graphs and of Their Complements
by: Caoduro, Marco, et al.
Published: (2025)

Graphs with core(G) = nucleus(G)
by: Levit, Vadim E., et al.
Published: (2026)

New Optimal Results on Codes for Location in Graphs
by: Junnila, Ville, et al.
Published: (2023)

Fractional Chromatic Numbers from Exact Decision Diagrams
by: Brand, Timo, et al.
Published: (2024)

On λ-backbone coloring of cliques with tree backbones in linear time
by: Michalik, Krzysztof, et al.
Published: (2021)

Induced subgraph density. III. Cycles and subdivisions
by: Nguyen, Tung, et al.
Published: (2023)

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
by: Loth, Jesse Campion, et al.
Published: (2022)

Some Thoughts on Graph Similarity
by: Grohe, Martin
Published: (2024)

Burling graphs revisited, part II: Structure
by: Pournajafi, Pegah, et al.
Published: (2021)

Completely Independent Spanning Trees in Split Graphs: Structural Properties and Complexity
by: Lalou, Mohammed, et al.
Published: (2025)

Open Packing in Graphs: Bounds and Complexity
by: Shalu, M. A., et al.
Published: (2024)

Census Dual Graphs: Properties and Random Graph Models
by: Anderson, Sara, et al.
Published: (2026)

Singular Values Versus Expansion in Directed and Undirected Graphs
by: Ruotolo, Jake, et al.
Published: (2025)

On Strict Brambles
by: Lardas, Emmanouil, et al.
Published: (2022)

Models of random spanning trees
by: Babson, Eric, et al.
Published: (2024)

Compact Representation of Semilinear and Terrain-like Graphs
by: Cardinal, Jean, et al.
Published: (2025)

Algorithmic Applications of Tyshkevich's Graph Decomposition: A Primer and a Toolkit
by: Cheng, Christine T., et al.
Published: (2026)

Induced subgraph density. IV. New graphs with the Erdős-Hajnal property
by: Nguyen, Tung, et al.
Published: (2023)

A first view on the density of 5-planar graphs
by: Büngener, Aaron, et al.
Published: (2025)