Critically paintable, choosable or colorable graphs

We extend results about critically k -colorable graphs to choosability and paintability (list colorability and on-line list colorability). Using a strong version of Brooks’ Theorem, we generalize Gallai’s Theorem about the structure of the low-degree subgraph of critically k -colorable graphs, and introduce a more adequate lowest-degree subgraph. We prove lower bounds for the edge density of critical graphs, and generalize Heawood’s Map-Coloring Theorem about graphs on higher surfaces to paintability. We also show that on a fixed given surface, there are only finitely many critically k -paintable/ k -choosable/ k -colorable graphs, if k ≥ 6 . In this situation, we can determine in polynomial time k -paintability, k -choosability and k -colorability, by giving a polynomial time coloring strategy for “Mrs. Correct”. Our generalizations of k -choosability theorems also concern the treatment of non-constant list sizes (non-constant k ). Finally, we use a Ramsey-type lemma to deduce all 2-paintable, 2-choosable, critically 3-paintable and critically 3-choosable graphs, with respect to vertex deletion and to edge deletion.