IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

The Goldberg-Seymour Conjecture and Gupta's Co-density Conjecture

  • Sept. 20, 2019
  • 2:30 p.m.
  • LeConte 312

Abstract

Given a multigraph $G = (V,E)$, the edge-coloring problem (ECP) is to color the edges of $G$ with the minimum number of colors such that no two incident edges receive the same color. The minimum number of colors needed for such a coloring of $G$ is called the chromatic index of $G$, written $\chi'(G)$.

By a result of Holyer, ECP is an $NP$-hard optimization problem. The $NP$-hardness gives rise to the necessity of finding near-optimal solutions and conditions under which $\chi'(G)$ can be determined exactly in polynomial time.

Let $\Delta(G)$ be the maximum degree of $G$ and let $ \Gamma(G) := \textrm{max}\{\frac{2 |E(U)|}{|U| - 1} : U \subseteq V, |U| \ge 3 \textrm{ and odd} \}$. $\Gamma(G)$ is called the density of $G$.

Clearly, the density is a lower bound for $\chi'(G)$. Moreover, this value can be computed in polynomial time. In the early 1970s Goldberg and Seymour independently conjectured that $\chi'(G) \le$ max$\{\Delta(G) + 1, \lceil \Gamma(G) \rceil \}$, known as the Goldberg-Seymour Conjecture.

On the other hand, the cover index $\chi^c(G)$ of $G$ is the greatest integer $k$ for which there is a coloring of $E$ with $k$ colors such that each vertex of $G$ is incident with at least one edge of each color. Let $\delta(G)$ be the minimum degree of $G$, let $E^+(U)$ be the set of all edges of $G$ with at least one end in $U$ for each $U \subseteq V$, and let $\Gamma^c(G)$ be the co-density of $G$, defined by $\Gamma^c(G) = \textrm{min} \{ \frac{2|E^+(U)|}{|U| + 1} : U \subseteq V, |U| \ge 3 \textrm{ and odd} \} $. In 1978 Gupta conjectured that $\chi'(G) \ge \textrm{min} \{ \delta(G) - 1, \lfloor \Gamma^c(G) \rfloor \} $, known as Gupta's co-density conjecture. In this talk, we will discuss some recent development on these two conjectures.

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