On cuts of small chromatic number in sparse graphs

2025/10/02 by Aubian, Guillaume, Bonamy, Marthe, Bourneuf, Romain +2 · 2 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2510.01791

Abstract

For a given integer k, let ℓ_k denote the supremum ℓ such that every sufficiently large graph G with average degree less than 2ℓ admits a separator X ⊆ V(G) for which χ(G[X]) < k. Motivated by the values of ℓ₁, ℓ₂ and ℓ₃, a natural conjecture suggests that ℓ_k = k for all k. We prove that this conjecture fails dramatically: asymptotically, the trivial lower bound ℓ_k ≥ \tfrack2 is tight. More precisely, we prove that for every ε>0 and all sufficiently large k, we have ℓ_k ≤ (1+ε)\tfrack2.

Citations

• On forest and bipartite cuts in sparse graphs
• Revisiting Extremal Graphs Having No Stable Cutsets
• Extremal Problems on Forest Cuts and Acyclic Neighborhoods in Sparse Graphs
• Forest Cuts in Sparse Graphs
• Sparse vertex cutsets and the maximum degree
• Bipartite independence number in graphs with bounded maximum degree

Cited by

• Degenerate Vertex Cuts in Sparse Graphs
• Cyclic Neighborhoods in Digraphs

Related

• Colouring Graphs with Sparse Neighbourhoods: Bounds and Applications
• Sparse Partitions of Graphs with Bounded Clique Number
• Bounds for the independence and chromatic numbers of locally sparse graphs
• Cycles in Sparse Graphs II
• Bounding χ by a fraction of Δ for graphs without large cliques