Nathan Kahl
Seton Hall
Strongest Monotone Degree Conditions and Bounds
Abstract:
In 1972 Chvatal gave a monotone degree condition for a degree sequence $\pi$ to be forcibly hamiltonian, i.e., if $\pi$ satisfies the condition, then every realization of $\pi$ is hamiltonian. In addition, if $\pi$ fails to satisfy the condition, then $\pi$ is majorized by a sequence $\pi$ that is not forcibly hamiltonian. A short while later, Bondy and Boesch developed a similarly strong monotone degree condition that guarantees a graph is $k$-connected. We call such monotone degree conditions "weakly optimal." For many graph properties the problem of finding "optimal" degree conditions--that is, conditions that identify every degree sequence that forcibly has the property--appears intractible.
In this talk we provide a framework to show how this idea can be used to find strongest monotone degree conditions for other graph properties, e.g., a perfect matching (1-factor) and a 2-factor. We then show how this framework can also be used to identify the best monotone degree bounds for various graph parameters, e.g., chromatic number, clique number, and independence number.