Separating polynomial -boundedness from -boundedness

Abstract: Extending the idea from the recent paper by Carbonero, Hompe, Moore, and Spirkl, for every function

f c o l o n m a t h b b N o m a t h b b N c u p i n f t y

with

f (1) = 1

and

, we construct a hereditary class of graphs

m a t h c a l G

such that the maximum chromatic number of a graph in

m a t h c a l G

with clique number

n

is equal to

f (n)

for every

n i n m a t h b b N

. In particular, we prove that there exist hereditary classes of graphs that are

c h i

-bounded but not polynomially

c h i

-bounded.

Recommendations

Cited in

(10)

This page was built for publication: Separating polynomial \(\chi\)-boundedness from \(\chi\)-boundedness