## Bounds on the defective, multi-fold, list chromatic number of planar graphs via Alon-Tarsi number

## Speaker

## Abstract

We prove the following technical theorem: The lexicographical product of a planar graph and has a matching with no edge of the form , , such that the Alon-Tarsi number of is at most .

Let be a graph and be natural numbers. A -list assignment is a map that assigns a -set to each vertex of . A -defective,\textit{-fold, -coloring} of is a function that assigns to each vertex an -set so that the color class of each color induces a subgraph of with maximum degree at most . For a defective coloring, an edge is a *flaw* if its ends have the same color. The theorem and known results concerning the Alon-Tarsi number yield the corollary:

For every planar graph there is a set of edges inducing a subgraph in with maximum degree such that for every -list assignment , there is a -defective, -fold, -coloring of whose flaws are contained in .

Indeed the corollary holds for on-line list coloring. This strengthens a result of Han, Kierstead, and Zhu by limiting the possible flaws to a set that is independent of the list assignment.

## Description

**Discrete math seminarFebruary 24, 2021**

**2:00pm MST**

**Online via Zoom**

**https://asu.zoom.us/j/81088074567?pwd=K25qeGpVY2gzTk5xS3RoNjkyWDNRZz09**

Password: DMS-S21