View source for LM hash

In [[graph theory]], a branch of [[mathematics]], '''list coloring''' is a type of [[graph coloring]] where each vertex can be restricted to a list of allowed colors, first studied by [[Vadim G. Vizing|Vizing]] <ref name="vizing">{{citation|authorlink=Vadim G. Vizing|last=Vizing|first=V. G.|year=1976|title=Vertex colorings with given colors|language=Russian|journal=Metody Diskret. Analiz.|volume=29|pages=3–10}}</ref> and by [[Paul Erdős|Erdős]], [[Arthur Rubin|Rubin]], and Taylor.<ref name="erdos">{{citation|last1=Erdős|first1=P.|author1-link=Paul Erdős|last2=Rubin|first2=A. L.|author2-link=Arthur Rubin|last3=Taylor|first3=H.|year=1979|url=http://www.math-inst.hu/~p_erdos/1980-07.pdf|contribution=Choosability in graphs|title=Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata|series=Congressus Numerantium|volume=26|pages=125–157}}</ref><ref name="gutner">{{citation|doi=10.1016/0012-365X(95)00104-5|last=Gutner|first=Shai|year=1996|arxiv=0802.2668 |title=The complexity of planar graph choosability|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|volume=159|issue=1|pages=119–130}}.</ref><ref name="jensen">{{citation|last1=Jensen|first1=Tommy R.|last2=Toft|first2=Bjarne|year=1995|title=Graph coloring problems|location=New York|publisher=Wiley-Interscience|isbn=0-471-02865-7}}</ref>

==Definition==

Given a graph ''G'' and given a set ''L''(''v'') of colors for each vertex ''v'' (called a '''list'''), a '''list coloring''' is a ''choice function'' that maps every vertex ''v'' to a color in the list ''L''(''v'').  As with graph coloring, a list coloring is generally assumed to be '''proper''', meaning no two [[Adjacent vertex|adjacent vertices]] receive the same color.  A graph is '''''k''-choosable''' (or '''''k''-list-colorable''') if it has a proper list coloring no matter how one assigns a list of ''k'' colors to each vertex.  The '''choosability''' (or '''list colorability''' or '''list chromatic number''') ch(''G'') of a graph ''G'' is the least number ''k'' such that ''G'' is ''k''-choosable.

More generally, for a function ''f'' assigning a positive integer ''f''(''v'') to each vertex ''v'', a graph ''G'' is '''''f''-choosable''' (or '''''f''-list-colorable''') if it has a list coloring no matter how one assigns a list of ''f''(''v'') colors to each vertex ''v''.  In particular, if <math>f(v) = k</math> for all vertices ''v'', ''f''-choosability corresponds to ''k''-choosability.

==Example==
[[File:List-coloring-K-3-27.svg|thumb|300px|A list coloring instance on the [[complete bipartite graph]] ''K''<sub>3,27</sub> with three colors per vertex. No matter which colors are chosen for the three central vertices, one of the outer 27 vertices will be uncolorable, showing that the list chromatic number of ''K''<sub>3,27</sub> is at least four.]]
Let ''q'' be a positive integer, and let ''G'' be the [[complete bipartite graph]] ''K''<sub>''q'',''q''<sup>''q''</sup></sub>. Let the available colors be represented by the ''q''<sup>2</sup> different two-digit numbers in [[radix]] ''q''.
On one side of the bipartition, let the ''q'' vertices be given sets of colors {{nowrap|{''i''0, ''i''1, ''i''2, ...}}} in which the first digits are equal to each other, for each of the ''q'' possible choices of the first digit&nbsp;''i''.
On the other side of the bipartition, let the ''q<sup>q</sup>'' vertices be given sets of colors {{nowrap|{0''a'', 1''b'', 2''c'', ...}}} in which the first digits are all distinct, for each of the ''q<sup>q</sup>'' possible choices of the ''q''-tuple {{nowrap|(''a'', ''b'', ''c'', ...).}}
For instance, for ''q''&nbsp;=&nbsp;2, this construction produces the graph ''K''<sub>2,4</sub>. In this graph, the two vertices on one side of the bipartition have color sets {00,01} and {10,11} and the four vertices on the other side of the bipartition have color sets {00,10}, {00,11}, {01,10}, and {01,11}. The illustration shows a larger example of the same construction, with ''q''&nbsp;=&nbsp;3.

Then, ''G'' does not have a list coloring for ''L'': no matter what set of colors is chosen for the vertices on the small side of the bipartition, this choice will conflict with all of the colors for one of the vertices on the other side of the bipartition. For instance if the vertex with color set {00,01} is colored 01, and the vertex with color set {10,11} is colored 10, then the vertex with color set {01,10} cannot be colored.
Therefore, the list chromatic number of ''G'' is at least ''q''&nbsp;+&nbsp;1.<ref name="g96">{{citation
 | last = Gravier | first = Sylvain
 | doi = 10.1016/0012-365X(95)00350-6
 | issue = 1-3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1388650
 | pages = 299–302
 | title = A Hajós-like theorem for list coloring
 | volume = 152
 | year = 1996}}.</ref>

Similarly, if <math>n=\binom{2k-1}{k}</math>, then the complete bipartite graph ''K''<sub>n,n</sub> is not ''k''-choosable. For, suppose that 2''k''&nbsp;&minus;&nbsp;1 colors are available in total, and that, on a single side of the bipartition, each vertex has available to it a different ''k''-tuple of these colors than each other vertex. Then, each side of the bipartition must use at least ''k'' colors, for otherwise some vertex would remain uncolored, but this implies that some two adjacent vertices have the same color. In particular, the [[utility graph]] ''K''<sub>3,3</sub> has chromatic index at least three, and the graph ''K''<sub>10,10</sub> has chromatic index at least four.<ref name="erdos"/>

==Properties==

Choosability ch(''G'') satisfies the following properties for a graph ''G'' with ''n'' vertices, [[Graph coloring|chromatic number]] χ(''G''), and [[Glossary of graph theory|maximum degree]] Δ(''G''):
# ch(''G'') ≥ χ(''G'').  A ''k''-list-colorable graph must in particular have a list coloring when every vertex is assigned the same list of ''k'' colors, which corresponds to a usual ''k''-coloring.
# ch(''G'') cannot be bounded in terms of chromatic number in general, that is, ch(''G'') ≤ ''f''(χ(''G'')) does not hold in general for any function ''f''.  In particular,  as the complete bipartite graph examples show, there exist graphs with χ(''G'')&nbsp;=&nbsp;2 but with ch(''G'') arbitrarily large.<ref name="g96"/>
# ch(''G'') ≤ χ(''G'') ln(''n'').<ref>{{Citation
  | last = Eaton 
  | first = Nancy
  | title = On two short proofs about list coloring - Part 1
  | work = Talk
  | year = 2003
  | url = http://www.math.uri.edu/~eaton/TalkUriOct03P1.pdf
  | accessdate = May 29, 2010}}
</ref><ref>{{Citation
  | last = Eaton 
  | first = Nancy
  | title = On two short proofs about list coloring - Part 2
  | work = Talk
  | year = 2003
  | url = http://www.math.uri.edu/~eaton/TalkUriOct03P2.pdf
  | accessdate = May 29, 2010}}
</ref>
# ch(''G'') ≤ Δ(''G'') + 1.<ref name="vizing"/><ref name="erdos"/>
# ch(''G'') ≤ 5 if ''G'' is a [[planar graph]].<ref name="thomassen">{{citation|last=Thomassen|first=Carsten|authorlink=Carsten Thomassen|year=1994|title=Every planar graph is 5-choosable|journal=Journal of Combinatorial Theory, Series B|volume=62|pages=180–181}}</ref>
# ch(''G'') ≤ 3 if ''G'' is a [[bipartite graph|bipartite]] planar graph.<ref name="alon">{{citation|doi=10.1007/BF01204715|last1=Alon|first1=Noga|author1-link=Noga Alon|last2=Tarsi|first2=Michael|year=1992|title=Colorings and orientations of graphs|journal=Combinatorica|volume=12|pages=125–134}}</ref>

==Computing choosability and (a,b)-choosability==

Two algorithmic problems have been considered in the literature:
# ''k''-''choosability'': decide whether a given graph is ''k''-choosable for a given ''k'', and
# (''j'',''k'')-''choosability'': decide whether a given graph is ''f''-choosable for a given function <math>f : V \to \{j,\dots,k\}</math>.
It is known that ''k''-choosability in bipartite graphs is <math>\Pi^p_2</math>-complete for any ''k'' ≥ 3, and the same applies for 4-choosability in planar graphs, 3-choosability in planar [[triangle-free graph]]s, and (2,3)-choosability in [[bipartite graph|bipartite]] planar graphs.<ref name="gutner"/><ref name="GutnerTarsi">{{citation|last1=Gutner|first1=Shai|last2=Tarsi|first2=Michael|year=2009|doi=10.1016/j.disc.2008.04.061|title=Some results on (''a'':''b'')-choosability|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|volume=309|issue=8|pages=2260–2270}}</ref> For P<sub>5</sub>-free graphs, that is, graphs [[forbidden graph characterization|excluding]] a 5-vertex [[path graph]], ''k''-choosability is [[fixed-parameter tractable]].
<ref>{{citation
 | last1 = Heggernes | first1 = Pinar
 | last2 = Golovach | first2 = Petr
 | contribution = Choosability of P<sub>5</sub>-free graphs
 | doi = 
 | pages = 382–391
 | publisher = Springer-Verlag
 | series = Lecture Notes on Computer Science
 | title = [[Mathematical Foundations of Computer Science]]
 | url = http://www.ii.uib.no/~pinar/Choosability.pdf
 | volume = 5734
 | year = 2009}}
</ref>

It is possible to test whether a graph is 2-choosable in [[linear time]] by repeatedly deleting vertices of degree zero or one until reaching the [[Degeneracy (graph theory)|2-core]] of the graph, after which no more such deletions are possible. The initial graph is 2-choosable if and only if its 2-core is either an even cycle or a [[theta graph]] formed by three paths with shared endpoints, with two paths of length two and the third path having any even length.<ref name="erdos"/>

==Applications==

List coloring arises in practical problems concerning channel/frequency assignment.{{Citation needed|date=September 2008}}
<!--there are several possibilities, e.g. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=570312-->

== See also ==
{{Wiktionary|choosability}}
* [[List edge-coloring]]

== References ==
<references/>

'''Further reading'''
*{{Citation | author=Aigner, Martin; Ziegler, Günter | title=Proofs from THE BOOK | publisher=Springer-Verlag | location=Berlin, New York | year=2009 | edition=4th | isbn=978-3-642-00855-9}}, Chapter 34 ''Five-coloring plane graphs''.
*Diestel, Reinhard. ''Graph Theory''. 3rd edition, Springer, 2005. Chapter 5.4 ''List Colouring''.<!--(sic! British English)--> [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.pdf electronic edition available for download]

{{DEFAULTSORT:List Coloring}}
[[Category:Graph coloring]]