Chi-bounded

Summary

In graph theory, a $\chi$-bounded (using the Greek letter chi) family $\mathcal{F}$ of graphs is one for which there is some function $f$ such that, for every integer $t$ the graphs in $\mathcal{F}$ with $t=\omega(G)$ (clique number) can be colored with at most $f(t)$ colors. The function $f(t)$ is called a $\chi$-binding function for $\mathcal{F}$. These concepts and their notations were formulated by András Gyárfás. The use of the Greek letter chi in the term $\chi$-bounded is based on the fact that the chromatic number of a graph $G$ is commonly denoted $\chi(G)$. An overview of the area can be found in a survey of Alex Scott and Paul Seymour.