The asymptotic behavior of the correspondence chromatic number

Alon (2000) proved that for any graph G, χℓ(G)=Ω(lnd), where χℓ(G) is the list chromatic number of G and d is the average degree of G. Dvořák and Postle (2015) recently introduced a generalization of list coloring, which they called correspondence coloring. We establish an analog of Alon’s result fo...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2016-11, Vol.339 (11), p.2680-2692
Main Author: Bernshteyn, Anton
Format: Article
Language:English
Subjects:
Asymptotic properties
Average degree
Coloring
Constants
Correspondence coloring
Graphs
List coloring
Lists
Mathematical analysis
Triangle-free graphs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Alon (2000) proved that for any graph G, χℓ(G)=Ω(lnd), where χℓ(G) is the list chromatic number of G and d is the average degree of G. Dvořák and Postle (2015) recently introduced a generalization of list coloring, which they called correspondence coloring. We establish an analog of Alon’s result for correspondence coloring; namely, we show that χc(G)=Ω(d/lnd), where χc(G) denotes the correspondence chromatic number of G. We also prove that for triangle-free G, χc(G)=O(Δ/lnΔ), where Δ is the maximum degree of G (this is a generalization of Johansson’s result about list colorings (Johansson, 1996)). This implies that the correspondence chromatic number of a regular triangle-free graph is, up to a constant factor, determined by its degree.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2016.05.012