List Coloring with a Bounded Palette

DOI10.1002/JGT.22013MaRDI QIDQ2958200zbMATH OpenOpenAlexFDO

Authors Marthe Bonamy, Ross J. Kang

Publication date 1 February 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringlist coloringprobabilistic method

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Kr'al' and Sgall (2005) introduced a refinement of list colouring where every colour list must be subset to one predetermined palette of colours. We call this $(k,ell)$-choosability when the palette is of size at most $ell$ and the lists must be of size at least $k$. They showed that, for any integer $kge2$, there is an integer $C=C(k,2k-1)$, satisfying $C=O(16^{k}lnk)$ as $koinfty$, such that, if a graph is $(k,2k-1)$-choosable, then it is $C$-choosable, and asked if $C$ is required to be exponential in $k$. We demonstrate it must satisfy $C=Omega(4^k/sqrtk)$. For an integer $ellge2k-1$, if $C(k,ell)$ is the least integer such that a graph is $C(k,ell)$-choosable if it is $(k,ell)$-choosable, then we more generally supply a lower bound on $C(k,ell)$, one that is super-polynomial in $k$ if $ell=o(k^2/lnk)$, by relation to an extremal set theoretic property. By the use of containers, we also give upper bounds on $C(k,ell)$ that improve on earlier bounds if $ellge2.75k$.

Recommendations

• Coloring graphs from lists with bounded size of their union
• scientific article; zbMATH DE number 2191977
• scientific article; zbMATH DE number 1735786
• Partial list colorings
• Choosability with union separation
• Extension from precoloured sets of edges
• Filling the complexity gaps for colouring planar and bounded degree graphs
• On the list coloring version of Reed's conjecture
• List colourings of graphs
• The chromatic polynomial and list colorings

Cites work

• A note on random greedy coloring of uniform hypergraphs
• Coloring graphs from lists with bounded size of their union
• Coloring, sparseness and girth
• scientific article; zbMATH DE number 1496580 (Why is no real title available?)
• Hypergraph containers
• Improper choosability and property B
• Improved bounds and algorithms for hypergraph 2-coloring
• Independent sets in hypergraphs
• List colourings of regular hypergraphs
• On the choosability of complete multipartite graphs with part size three

Cited in

(7)

• Proportional 2-choosability with a bounded palette
• List-colourings
• A note on list-coloring powers of graphs
• Coloring graphs from lists with bounded size of their union
• Minimal abundant packings and choosability with separation
• Exact and parameterized algorithms for choosability
• Asymmetric list sizes in bipartite graphs

This page was built for publication: List Coloring with a Bounded Palette

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