IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Towards Vizing's Independence Number Conjecture

  • March 28, 2014
  • 11 a.m.
  • LeConte 312


The \emph{chromatic index} $\chi '$ of a graph is the minimum number of colors needed to properly color its edges and is equal to either $\Delta$ or $\Delta + 1$ where $\Delta$ is the maximum degree of the graph. A graph with maximum degree $\Delta$ is \emph{edge critical} if $\chi '(G-e) = \chi'(G)-1$ for every edge $e$. The \emph{independence number} $\alpha$ of a graph is the cardinality of a largest set of vertices which are pairwise non-adjacent. For edge critical graphs with $n$ vertices, Vizing conjectured that $\alpha(G) \leq n/2$. For these graphs, Woodall has shown that $\alpha (G) \leq 3n/5$ and better results exist for specific values of $\Delta$. We discuss a new approach using the Independence Decomposition Theorem: namely that any graph can be decomposed into unique subgraphs having certain nice properties. We present some of our relevant results as well as apply our new approach to edge critical graphs with $\Delta=3$.

Joint work with Craig Larson (VCU), Bethany Turner (NC State), and Carl Yerger (Davidson).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster