Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness
2023
Online
report
Zugriff:
A class $\mathcal F$ of graphs is $\chi$-bounded if there is a function $f$ such that $\chi(H)\le f(\omega(H))$ for all induced subgraphs $H$ of a graph in $\mathcal F$. If $f$ can be chosen to be a polynomial, we say that $\mathcal F$ is polynomially $\chi$-bounded. Esperet proposed a conjecture that every $\chi$-bounded class of graphs is polynomially $\chi$-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are $\chi$-bounded but not polynomially $\chi$-bounded. Nevertheless, inspired by Esperet's conjecture, we introduce Pollyanna classes of graphs. A class $\mathcal C$ of graphs is Pollyanna if $\mathcal C\cap \mathcal F$ is polynomially $\chi$-bounded for every $\chi$-bounded class $\mathcal F$ of graphs. We prove that several classes of graphs are Pollyanna and also present some proper classes of graphs that are not Pollyanna.
Comment: 35 pages, 12 figures
Titel: |
Reuniting $\chi$-boundedness with polynomial $\chi$-boundedness
|
---|---|
Autor/in / Beteiligte Person: | Chudnovsky, Maria ; Cook, Linda ; Davies, James ; Oum, Sang-il |
Link: | |
Veröffentlichung: | 2023 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|