We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Polynomial chi-boundedness

Formal Metadata

Title
Polynomial chi-boundedness
Title of Series
Number of Parts
24
Author
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
A graph $G$ is $\chi$-bounded by the function $f$ if every induced subgraph $H$ of $G$ satisfied $\chi(H) \le f(\omega(H))$. A class of graphs is $\chi$-bounded if there exists a function $f$ such that every graph in the class is $\chi$-bounded by $f$. It is polynomially $\chi$-bounded if there is such a function $f$ that is a polynomial. Some classes of graphs are $\chi$-bounded, some are not. It is not known whether there exists a hereditary class of graph that is $\chi$-bounded but not polynomially $\chi$-bounded. The goal of this talk is to survey several results, proof techniques, and open questions around the notion of polynomial $\chi$-boundedness.
Keywords