TY - JOUR

T1 - Critically paintable, choosable or colorable graphs

AU - Schauz, Uwe

AU - Riasat, Ayesha

N1 - Funding Information:
We want to thank the Abdus Salam School of Mathematical Sciences for providing a good research environment. The second author also gratefully acknowledges the support provided by the King Fahd University of Petroleum and Minerals under the project numbers FT090010.

PY - 2012/11/28

Y1 - 2012/11/28

N2 - 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.

AB - 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.

KW - Critical graph

KW - Graph coloring

KW - Graphs on surfaces

KW - List coloring

KW - Paintability

UR - http://www.scopus.com/inward/record.url?scp=84865344445&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2012.07.035

DO - 10.1016/j.disc.2012.07.035

M3 - Article

AN - SCOPUS:84865344445

SN - 0012-365X

VL - 312

SP - 3373

EP - 3383

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 22

ER -