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