Fractional DP-colorings of sparse graphs

Anton Bernshteyn, Alexandr Kostochka, Xuding Zhu

Research output: Contribution to journalArticlepeer-review

Abstract

DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořák and Postle [J. Combin. Theory Ser. B 129 (2018), pp. 38–54]. In this paper we introduce and study the fractional DP-chromatic number (Formula presented.). We characterize all connected graphs (Formula presented.) such that (Formula presented.) : they are precisely the graphs with no odd cycles and at most one even cycle. By a theorem of Alon, Tuza, and Voigt [Discrete Math. 165–166 (1997), pp. 31–38], the fractional list-chromatic number (Formula presented.) of any graph (Formula presented.) equals its fractional chromatic number (Formula presented.). This equality does not extend to fractional DP-colorings. Moreover, we show that the difference (Formula presented.) can be arbitrarily large, and, furthermore, (Formula presented.) for every graph (Formula presented.) of maximum average degree (Formula presented.). On the other hand, we show that this asymptotic lower bound is tight for a large class of graphs that includes all bipartite graphs as well as many graphs of high girth and high chromatic number.

Original languageEnglish (US)
Pages (from-to)203-221
Number of pages19
JournalJournal of Graph Theory
Volume93
Issue number2
DOIs
StatePublished - Feb 1 2020

Keywords

  • DP-coloring
  • d-degenerate graph
  • fractional coloring

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Fractional DP-colorings of sparse graphs'. Together they form a unique fingerprint.

Cite this