Degree Sequences and k-Factors
by
Nathan Kahl
Seton Hall University
Coauthors: Doug Bauer (Stevens Institute of Technology), Ed Schmeichel (San Jose State University)

In 1972 Chvatal gave a monotone degree condition for a degree sequence p to be forcibly hamiltonian, i.e., if p satisfies the condition, then every realization of p is hamiltonian. In addition, if p fails to satisfy the condition, then p is majorizd by a sequence p' 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."

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.

Date received: April 4, 2008