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

-

## Locations

Online Seminar

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

## Event Contact

Co-Director, M.S. in Computational Decision Science and Operations Research (CDSOR) Associate Professor of Applied Mathematics
312.567.3128