The Asymptotic χ \chi -Boundedness of Hereditary Families

Bruce Reed, Yelena Yuditsky · 2025

Read The Asymptotic χ \chi -Boundedness of Hereditary Families by Bruce Reed, Yelena Yuditsky (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01070.txt.

Introduction

Bruce Reed and Yelena Yuditsky ask when a family of graphs that avoids a fixed pattern is almost always easy to color. A hereditary family keeps every graph that can be carved out of a member. The coloring question links two numbers: the colors a graph needs and the size of its largest clique, its tightest fully linked set. Their notion weakens an older one: nearly every graph in the family, not literally every one, must obey the bound.

For every forbidden tree pattern, almost all avoiding graphs turn out to need exactly as many colors as their clique size, the best possible. The same holds for forbidden cycles of every length but one. The exception, the six-cycle, still obeys a bound slightly above its clique size, with a logarithmic discount. The authors also discuss nearby questions the results open up.

Catalog record

CREATORBruce Reed, Yelena Yuditsky
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-01070

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Asymptotic χ \chi -Boundedness of Hereditary Families Bruce Reed, Yelena Yuditsky Abstract A family ℱ {\cal F} of graphs is asymptotically χ \chi -bounded with bounding function f f if almost every graph G G in the family satisfies χ ⁡ ( G ) ≤ f ⁡ ( ω ⁡ ( G ) ) \chi(G)\leq f(\omega(G)) . A graph is H H -free if it does not contain H H as an induced subgraph. We ask which hereditary families are asymptotically χ \chi -bounded, and discuss some related questions. We show that for every tree T T , almost all T T -free graphs G G satisfy χ ⁡ ( G ) = ω ⁡ ( G ) \chi(G)=\omega(G) . We show that for every cycle C k C_{k} except C 6 C_{6} , almost every C k C_{k} -free graph G G satisfies χ ⁡ ( G ) = ω ⁡ ( G ) \chi(G)=\omega(G) . We show that the C 6 C_{6} -free graphs are asymptotically χ \chi -bounded with bounding function f ⁡ ( w ) = ( 1 + o ⁡ ( 1 ) ) ​ w 2 log ⁡ w f(w)=(1+o(1))\frac{w^{2}}{\log w} . 1 Overview The clique number 1 1 1 For this and other standard notation and terminology see Bondy and Murty [ 4 ] . , \omega(G) , of a graph G is a lower bound on its chromatic number, \chi(G) . On the other hand, there is no upper bound on the chromatic number which is solely a function of its clique number. Indeed, there are graphs of clique number two which have arbitrarily high chromatic number. The first construction of such graphs was given by Zykov [ 32 ] in 1949. A natural and well studied question is to determine for which families {\cal F} , \chi(G) is bounded by \omega(G) or some function of it, for those G in {\cal F} . A family {\cal F} is called \chi -bounded with bounding function f , if every G\in{\cal F} satisfies \chi(G)\leq f(\omega(G)) . Perhaps the most renowned \chi -bounded family is the perfect graphs. Definition . A graph is G is perfect if every induced subgraph F of G satisfies: \chi(F)=\omega(F) . Theorem 1 . (The Strong Perfect Graph Theorem, [ 7 ] ) A graph is perfect if and only if for all k\geq 2 it contains no induced subgraph isomorphic to the odd cycle C_{2k+1} or its complement \overline{C_{2k+1}} . We focus on families of graphs for which almost all 2 2 2 a property holds for almost all graphs in a family if the proportion of graph of size n in the family for which it fails goes to zero as n goes to infinity. graphs in the family satisfy \chi(G)\leq f(\omega(G)) for some function f . We say such a family is asymptotically \chi -bounded with bounding function f . We discuss hereditary families {\cal F} . This means that {\cal F} is closed under the taking of induced subgraphs or equivalently for some set O_{\cal F} of obstructions, a graph is in {\cal F} precisely if it has no obstruction in O_{\cal F} as an induced subgraph. Our main results are the following: Definition . A graph is H -free if it does not contain H as an induced subgraph. Theorem 2 . Let T be a tree, then almost all T -free graphs G have \chi(G)=\omega(G) . Theorem 3 . For any k\neq 6 , almost all C_{k} -free graphs G have \chi(G)=\omega(G) . Theorem 4 . The C_{6} -free graphs G are asymptotically \chi -bounded with a bounding function f(w)=(1+o(1))\frac{w^{2}}{\log w} . Our approach to proving Theorems 2 , 3 , and 4 builds on that taken by Prömel and Steger in [ 22 ] to prove Theorem 3 for k\in\{4,5\} . The key to their proof for k=5 is the following result: Theorem 5 . The vertex set of almost every C_{5} -free graph can be partitioned into V_{1} and V_{2} such that either (i) V_{1} induces a clique and V_{2} induces a disjoint union of cliques, or (ii) V_{1} is a stable set and V_{2} is complete multi-partite. This result can be used to obtain the following strengthening of Theorem 3 for k=5 . Corollary 6 . Almost all C_{5} -free graphs G are perfect. Proof. For k\geq 2 , when we delete a clique from C_{2k+1} , we are left with a graph containing P_{3} (in fact P_{2k-1} ) as an induced subgraph. Thus, when we delete a stable set from \overline{C_{2k+1}} , we are left with a graph containing \overline{P_{3}} as an induced subgraph. When we delete a stable set from C_{2k+1} we are left with a graph containing \overline{P_{3}} as an induced subgraph. Thus when we delete a clique from \overline{C_{2k+1}} we are left with a graph containing P_{3} as an induced subgraph. Hence, if a graph has a partition satisfying either of (i) or (ii) in Theorem 5 , it cannot contain C_{2k+1} or \overline{C_{2k+1}} as an induced subgraph. By the Strong Perfect Graph Theorem, we are done. ∎ We remark that since the Strong Perfect Graph Theorem had not proven when Prömel and Steger proved their result, they provided a slightly longer but still straightforward proof that graphs whose vertex set can be partitioned into a clique and the disjoint union of cliques is perfect. Partitioning results similar to Theorem 5 will be useful in proving Theorems 2 and 3 . However, we need to develop new techniques for moving from a partition to \chi -boundedness, as the ad-hoc argument used in the proof of Corollary 6 is not really of general application. In Section 2 , we discuss the partitioning results and how they might be exploited. In Section 5 , we use this approach to prove Theorems 2 and 3 . In Section 6 we discuss how these asymptotic colourings can be extended to other hereditary families of graphs. In the remainder of this section, we explain why H -free graphs for H a tree or a cycle are of particular interest. Before doing so we remark that Erdős, Kleitman and Rothschild [ 11 ] proved that almost every triangle free graph is bipartite and hence perfect while Prömel and Steger [ 19 ] proved that almost every C_{4} free graph is the disjoint union of a clique and a stable set and hence perfect. 1.1 Why Trees and Cycles? To motivate our focus on trees and cycles, we briefly survey some key results on the \chi -boundedness of hereditary families. If {\cal F} is a hereditary family whose members satisfy \chi=\omega then they satisfy a stronger property, all of their induced subgraphs H satisfy \chi(H)=\omega(H) . In 1961 [ 2 ] , motivated by a question of Shannon about the zero-error transmission rate of a noisy channel, Berge initiated the study of graphs with this property. He called such graphs perfect . Berge noted that for any k\geq 2 , the cycle C_{2k+1} satisfies \omega(C_{2k+1})=2 and \chi(C_{2k+1})=3 . He also noted that \omega(\overline{C_{2k+1}})=k and \chi(\overline{C_{2k+1}})=k+1 . Thus if a graph is to be perfect it can contain neither a cycle of odd

Read the complete text