Jump to content

List coloring: Difference between revisions

From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
Edemaine (talk | contribs)
492 edits
→Properties: add possible reference for Fact
Cold Light (talk | contribs)
214 edits
No edit summary
Line 1: Line 1:
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 Vizing <ref name="vizing">Vizing, V. G. (1976). Vertex colorings with given colors (in Russian). ''Metody Diskret. Analiz.'' '''29''', 3–10.</ref> and by Erdős, Rubin, and Taylor <ref name="erdos">Erdős, P.; Rubin, A. L.; Taylor, H. (1979). Choosability in graphs. In ''Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata'', ''Congr. Num. 26'', 125–157.</ref>.<ref name="gutner">Gutner, Shai (1996). [http://arxiv.org/abs/0802.2668 The complexity of planar graph choosability]. ''Discrete Math.'' 159(1):119–130.</ref><ref name="jensen">Jensen, Tommy R.; Toft, Bjarne (1995). ''Graph coloring problems''. New York: Wiley-Interscience. ISBN 0-471-02865-7.</ref>
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 Vizing <ref name="vizing">Vizing, V. G. (1976). Vertex colorings with given colors (in Russian). ''Metody Diskret. Analiz.'' '''29''', 3–10.</ref> and by Erdős, Rubin, and Taylor <ref name="erdos">Erdős, P.; Rubin, A. L.; Taylor, H. (1979). [http://www.math-inst.hu/~p_erdos/1980-07.pdf Choosability in graphs]. In ''Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata'', ''Congr. Num. 26'', 125–157.</ref>. <ref name="gutner">Gutner, Shai (1996). [http://arxiv.org/abs/0802.2668 The complexity of planar graph choosability]. ''Discrete Math.'' 159(1):119–130.</ref><ref name="jensen">Jensen, Tommy R.; Toft, Bjarne (1995). ''Graph coloring problems''. New York: Wiley-Interscience. ISBN 0-471-02865-7.</ref>


==Definition==
==Definition==

Revision as of 22:37, 10 November 2008

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 Vizing [1] and by Erdős, Rubin, and Taylor [2]. [3][4]

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 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 for all vertices v, f-choosability corresponds to k-choosability.

Properties

Choosability ch(G) satisfies the following properties for a graph G with n vertices, chromatic number χ(G), and maximum degree Δ(G):

  1. 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.
  2. 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.
  3. ch(G) ≤ χ(G) ln(n).[citation needed]
  4. ch(G) ≤ Δ(G) + 1. [1],[2]
  5. ch(G) ≤ 5 if G is a planar graph. [5]
  6. ch(G) ≤ 3 if G is a bipartite, planar graph. [6]

Computational complexity

Two algorithmic problems have been considered:

  1. k-choosability: decide whether a given graph is k-choosable for a given k, and
  2. (j,k)-choosability: decide whether a given graph is f-choosable for a given function .

It is known that k-choosability in bipartite graphs for any k ≥ 3, 4-choosability in planar graphs, 3-choosability in planar triangle-free graphs, and (2,3)-choosability in bipartite planar graphs are all -complete.[3]

Applications

List coloring arises in practical problems concerning channel/frequency assignment.[citation needed]

See also

Look up choosability in Wiktionary, the free dictionary.

References

  1. ^ a b Vizing, V. G. (1976). Vertex colorings with given colors (in Russian). Metody Diskret. Analiz. 29, 3–10.
  2. ^ a b Erdős, P.; Rubin, A. L.; Taylor, H. (1979). Choosability in graphs. In Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congr. Num. 26, 125–157.
  3. ^ a b Gutner, Shai (1996). The complexity of planar graph choosability. Discrete Math. 159(1):119–130.
  4. ^ Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
  5. ^ Thomassen, Carsten (1994). Every planar graph is 5-choosable. J. Combin. Theory (B) 64, 180–181.
  6. ^ Alon, Noga; Tarsi, Michael (1992). Colorings and orientations of graphs. Combinatorica 12, 125–134.
Retrieved from "https://en.wikipedia.org/w/index.php?title=List_coloring&oldid=250973159"