List coloring

List coloring

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]

Contents

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 f(v) = k 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).[5][6]
  4. ch(G) ≤ Δ(G) + 1.[1][2]
  5. ch(G) ≤ 5 if G is a planar graph.[7]
  6. ch(G) ≤ 3 if G is a bipartite planar graph.[8]

Computing choosability and (a,b)-choosability

Two algorithmic problems have been considered in the literature:

  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 f : V \to \{j,\dots,k\}.

It is known that k-choosability in bipartite graphs is \Pi^p_2-complete for any k ≥ 3, and the same applies for 4-choosability in planar graphs, 3-choosability in planar triangle-free graphs, and (2,3)-choosability in bipartite planar graphs.[3][9] For P5-free graphs, that is, graphs excluding a 5-vertex path graph, k-choosability is fixed-parameter tractable. [10]

Applications

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

See also

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", Proc. West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congressus Numerantium, 26, pp. 125–157, http://www.math-inst.hu/~p_erdos/1980-07.pdf 
  3. ^ a b Gutner, Shai (1996), "The complexity of planar graph choosability", Discrete Mathematics 159 (1): 119–130, arXiv:0802.2668, doi:10.1016/0012-365X(95)00104-5 .
  4. ^ Jensen, Tommy R.; Toft, Bjarne (1995), Graph coloring problems, New York: Wiley-Interscience, ISBN 0-471-02865-7 
  5. ^ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 1", Talk, http://www.math.uri.edu/~eaton/TalkUriOct03P1.pdf, retrieved May 29, 2010 
  6. ^ Eaton, Nancy (2003), "On two short proofs about list coloring - Part 2", Talk, http://www.math.uri.edu/~eaton/TalkUriOct03P2.pdf, retrieved May 29, 2010 
  7. ^ Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B 64: 180–181 
  8. ^ Alon, Noga; Tarsi, Michael (1992), "Colorings and orientations of graphs", Combinatorica 12: 125–134, doi:10.1007/BF01204715 
  9. ^ Gutner, Shai; Tarsi, Michael (2009), "Some results on (a:b)-choosability", Discrete Mathematics 309 (8): 2260–2270, doi:10.1016/j.disc.2008.04.061 
  10. ^ Heggernes, Pinar; Golovach, Petr (2009), "Choosability of P5-free graphs", Mathematical Foundations of Computer Science, Lecture Notes on Computer Science, 5734, Springer-Verlag, pp. 382–391, http://www.ii.uib.no/~pinar/Choosability.pdf 

Further reading

  • Aigner, Martin; Ziegler, Günter (2009), Proofs from THE BOOK (4th ed.), Berlin, New York: Springer-Verlag, 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. electronic edition available for download

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • List edge-coloring — In mathematics, list edge coloring is a type of graph coloring.More precisely, a list edge coloring is a choice function that maps every edge to a color from a prescribed list for that edge.A graph is k edge choosable if it has a proper list edge …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • List of conjectures — This is an incomplete list of mathematical conjectures. They are divided into four sections, according to their status in 2007. See also: * Erdős conjecture, which lists conjectures of Paul Erdős and his collaborators * Unsolved problems in… …   Wikipedia

  • List of children's non-fiction writers — List of authors who have written non fiction (informational) books for children. For a discussion of the criteria used to define something as a work of children s literature, see children s literature. Peter Ackroyd (UK) history David A. Adler… …   Wikipedia

  • List of Heroscape supplements — List of supplemental materials for Heroscape, a miniatures based strategy boardgame. =Sets=A list of the expansions and master sets, roughly in order of release. Wave releases as described above are noted, others are boxed releases: Rise of the… …   Wikipedia

  • List of Lieutenant Governors of Illinois — List of persons elected as Lieutenant Governor of Illinois and the Governor they served with. Illinois says Pat Quinn is the 45th Lt. Governor. [http://www.standingupforillinois.org/2007/about/history.php] Coloring is based on party of the… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • List of The Land Before Time episodes — This is the list of episodes of animated television series The Land Before Time , based on The Land Before Time feature length films.eason 1: 2007 2008DVDThemed DVDs{| border= 1 ! Title! Episodes! Bonus Features! Released! Aspect Ratio! Character …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”