Discrete Applied Math Seminar by Zimu Xiang: Equitable List Coloring of Sparse Graphs

Speaker:

Zimu Xiang, University of Illinois Urbana-Champaign

Title:

Equitable List Coloring of Sparse Graphs

Abstract:

A proper vertex coloring of a graph is equitable if the sizes of all color classes differ by at most $1$. For a list assignment $L$ or $r$ colors to each vertex of an $n$-vertex graph $G$, an equitable $L$-coloring of $G$ is a proper coloring of vertices of $G$ from their lists such that no color is used more than $\lceil n/r\rceil$ times. A graph is equitably $r$-choosable if it has an equitable $L$-coloring for every $r$-list assignment $L$. A graph is $(a,b)$-sparse if for every $A\subseteq V(G)$, the number of edges in the subgraph $G[A]$ of $G$ induced by $A$ is at most $a|A|+b$.

Our first result is that every $(7/6,1/3)$-sparse graph with minimum degree at least $2$ is equitably $3$-colorable and equitably $3$-choosable. Our second result is that every $(5/4,1/2)$-sparse graph with minimum degree at least $2$ is equitably $k$-colorable and equitably $k$-choosable for every $k\ge 4$. We also introduce the notion of strongly equitable list coloring as a combination of equitable coloring and equitable list coloring.

Discrete Applied Math Seminar

Request Zoom Link