The asymptotic χ-boundedness of hereditary families

2025/06/01 by Reed, Bruce, Yuditsky, Yelena · 2 citations
#05C80 05C15 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.2506.01070

Abstract

A family \cal F of graphs is asymptotically χ-bounded with bounding function f if almost every graph G in the family satisfies χ(G) ≤ f(ω(G)). A graph is H-free if it does not contain H as an induced subgraph. We ask which hereditary families are asymptotically χ-bounded, and discuss some related questions. We show that for every tree T, almost all T-free graphs G satisfy χ(G)=ω(G). We show that for every cycle C_k except C₆, almost every C_k-free graph G satisfies χ(G) = ω(G). We show that the C₆-free graphs are asymptotically χ-bounded with bounding function f(w)=(1+o(1))(w²)/(log w).

Citations

• The Global Structure of a Typical Graph Without H as an Induced Subgraph when H is a Cycle
• Typical structure of hereditary graph families. II. Exotic examples
• A survey of χ-boundedness
• A survey of χ‐boundedness
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• Almost all string graphs are intersection graphs of plane convex sets
• Induced subgraphs of graphs with large chromatic number. XII. Distant stars
• Forbidding induced even cycles in a graph: typical structure and counting

Cited by

• Chromatic numbers from edge ideals: Graph classes with vanishing syzygies are polynomially χ-bounded
• Cops and Robbers, Clique Covers, and Induced Cycles

Related

• Families of Linearly χ-bounded Graphs without Chair or its Induced Sub-graphs
• Chromatic bounds for some classes of 2K₂-free graphs
• On the chromatic number of some (P₃∪ P₂)-free graphs
• Degeneracy of P_t-free and C_{≥ t}-free graphs with no large complete bipartite subgraphs
• (δ, χ__{\sf FF})-bounded families of graphs