Classes of graphs with no long cycle as a vertex-minor are polynomially $\chi$-bounded
| Autor: | Kim, Ringi, Kwon, O-joung, Oum, Sang-il, Sivaraman, Vaidy |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | J. Combin. Theory Ser. B, 2019 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.jctb.2019.06.001 |
| Popis: | A class $\mathcal G$ of graphs is $\chi$-bounded if there is a function $f$ such that for every graph $G\in \mathcal G$ and every induced subgraph $H$ of $G$, $\chi(H)\le f(\omega(H))$. In addition, we say that $\mathcal G$ is polynomially $\chi$-bounded if $f$ can be taken as a polynomial function. We prove that for every integer $n\ge3$, there exists a polynomial $f$ such that $\chi(G)\le f(\omega(G))$ for all graphs with no vertex-minor isomorphic to the cycle graph $C_n$. To prove this, we show that if $\mathcal G$ is polynomially $\chi$-bounded, then so is the closure of $\mathcal G$ under taking the $1$-join operation. Comment: 15 pages, 2 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|