Georgia Institute of Technology College of Sciences

We say a class of graphs $\mathcal{F}$ is degree-bounded if there exists a function $f$ such that $\delta(G)\le f(\tau(G))$ for every $G\in\mathcal{F}$, where $\delta(G)$ denotes the minimum degree of $G$ and $\tau(G)$ is the biclique number of $G$, that is, the largest integer $t$ such that $G$ contains $K_{t,t}$ as a subgraph. Such a function $f$ is called a degree-bounding function for $\mathcal{F}$.

In joint work with Ant\'onio Gir\~ao, Zach Hunter, Rose McCarty and Alex Scott, we proved that every hereditary degree-bounded class $\mathcal{F}$ has a degree-bounding function that is singly exponential in the biclique number $\tau$. A more recent result by Ant\'onio Gir\~ao and Zach Hunter improved this bound to a polynomial function in $\tau$. In this talk, I will discuss examples and the recent results on degree-boundedness.