20260512 Linda Cook

A (proper) $k$-coloring of a graph $G$ is a function assigning a say{color} chosen from ${1,2, dots, k}$ to each of the vertices of the graph with the property that no two adjacent vertices receive the same color.
The chromatic number $chi(G)$ is the minimum $k$ for which there exists a $k$-coloring of $G$.
Testing $k$-colorability is a classic NP-Hard problem and graph coloring lies at the center of modern graph theory.

The say{dual parameter} to the chromatic number is the clique number $omega$.
A emph{clique} is a set of pairwise adjacent vertices in a graph.
It's easy to see that all vertices in a clique must all receive different colors in any proper coloring.
The emph{clique number} $omega(G)$ is the maximum size of a clique in $G$.
Trivially, $chi(G) geq omega(G)$.
Unfortunately, we cannot in general obtain any upper bound on the chromatic number in terms of the clique number.
There are classical constructions for graphs of triangle-free graphs with arbitrarily large chromatic number.
Moreover, it is s a well-known result of ErdH{o}s that for every $g geq 3$ there exist graphs with arbitrarily large chromatic number and with no cycle of length less than $g$.
Inspired by perfect graphs, the area of chi-boundedness seeks to understand what structural conditions admit such a bound.
This talk will introduce the general area of chi-boundedness and will survey some of the speakers work in the area.

No prior knowledge of graph theory will be assumed.