Adapted list coloring of graphs and hypergraphs

A. V. Kostochka, Xuding Zhu

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce and study adapted list coloring of graphs and hypergraphs. This is a generalization of ordinary list coloring and adapted coloring, and has more applications than these. We prove that the upper bounds on the adaptable choosability of graphs and uniform hypergraphs in terms of maximum degree are sufficiently stronger than those on the ordinary choosability, while the bounds in terms of degeneracy are the same. We also characterize simple graphs with adaptable choosability 2.

Original languageEnglish (US)
Pages (from-to)398-408
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Volume22
Issue number1
DOIs
StatePublished - 2008

Keywords

  • Adapted coloring
  • Degree conditions
  • List coloring

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Adapted list coloring of graphs and hypergraphs'. Together they form a unique fingerprint.

Cite this