The Johansson-Molloy theorem for DP-coloring

DOI10.1002/RSA.20811MaRDI QIDQ5229335zbMATH OpenOpenAlexFDO

Authors Anton Bernshteyn

Publication date 14 August 2019

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.03843

zbMATH Keywords

DP-coloringentropy compressiongraph coloringlist coloringlocal lemmatriangle-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The aim of this note is twofold. On the one hand, we present a streamlined version of Molloy's new proof of the bound $chi(G)leq(1+o(1))Delta(G)/lnDelta(G)$ for triangle-free graphs $G$, avoiding the technicalities of the entropy compression method and only using the usual "lopsided" Lov'asz Local Lemma (albeit in a somewhat unusual setting). On the other hand, we extend Molloy's result to DP-coloring (also known as correspondence coloring), a generalization of list coloring introduced recently by Dvov{r}'ak and Postle.

Recommendations

• Counting colorings of triangle-free graphs
• Coloring triangle-free graphs with local list sizes
• A note on a Brooks' type theorem for DP-coloring
• Defective DP-colorings of sparse simple graphs
• DP-colorings of graphs with high chromatic number

Cited in

(31)

• The list chromatic number of graphs with small clique number
• Combinatorial Nullstellensatz and DP-coloring of graphs
• Answers to two questions on the DP color function
• Cover and variable degeneracy
• A deletion-contraction relation for the DP color function
• The DP color function of joins and vertex-gluings of graphs
• Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
• On the chromatic polynomial and counting DP-colorings of graphs
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
• Partial DP-coloring of graphs
• Non-chromatic-adherence of the DP color function via generalized theta graphs
• Commutative algorithms approximate the LLL-distribution
• The -Ramsey problem for triangle-free graphs
• Coloring triangle-free graphs with local list sizes
• Colouring graphs with forbidden bipartite subgraphs
• Independent transversals in bipartite correspondence-covers
• Counting colorings of triangle-free graphs
• Every planar graph without 5-cycles adjacent to 6-cycles is DP-4-colorable
• Asymptotically good edge correspondence colourings
• scientific article; zbMATH DE number 7758308 (Why is no real title available?)
• Graph and hypergraph colouring via nibble methods: a survey
• Extremal bipartite independence number and balanced coloring
• Variable degeneracy on toroidal graphs
• On triangle-free list assignments
• An algebraic approach for counting DP-3-colorings of sparse graphs
• New bounds for odd colourings of graphs
• Coloring locally sparse graphs
• New bounds for proper h-conflict-free colorings
• On Vizing's problem for triangle-free graphs
• List colorings of k-partite k-graphs
• DP-coloring of graphs from random covers

This page was built for publication: The Johansson-Molloy theorem for DP-coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5229335)