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

Wednesday, February 24, 2021 - 2:00pm to 3:00pm
Online via Zoom


Ming Han
Arizona State University


We prove the following technical theorem: The lexicographical product G[K_{2}] of a planar graph G and K_{2}=(\{u,u'\},\{uu'\}) has a matching M with no edge of the form (v,u)(v,u'), v\in V, such that the Alon-Tarsi number of G[K_{2}]-M is at most 9.

Let G be a graph and d,m,k be natural numbers. A k-list assignment L is a map that assigns a k-set to each vertex of G. A d-defective,\textit{m-fold, L-coloring} of G is a function \phithat assigns to each vertex v\in V an m-set \phi(v)\subseteq L(v) so that the color class   \alpha\in\phi(v)\} of each color \alpha induces a subgraph of G with maximum degree at most d. 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 G there is a set F of edges inducing a subgraph in G with maximum degree 2 such that for every 9-list assignment L, there is 
a 1-defective, 2-fold, L-coloring of G whose flaws are contained in F.

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.


Discrete math seminar
February 24, 2021

2:00pm MST
Online via Zoom
Password: DMS-S21


Event Type