List coloring
Encyclopedia
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
and by Erdős
, Rubin
, and Taylor.
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.
χ(G), and maximum degree
Δ(G):
It is known that k-choosability in bipartite graphs is
-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
planar graphs. For P5-free graphs, that is, graphs excluding a 5-vertex path graph
, k-choosability is fixed-parameter tractable.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a branch of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, list coloring is a type of graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
where each vertex can be restricted to a list of allowed colors, first studied by Vizing
Vadim G. Vizing
Vadim Georgievich Vizing is a Ukrainian mathematician known for his contributions to graph theory, and especially for Vizing's theorem stating that the edges of any graph with maximum degree Δ can be colored with at most Δ + 1 colors.- Biography :Vizing was born in Kiev on March...
and by Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, Rubin
Arthur Rubin
Arthur Leonard Rubin is an American mathematician.-Biography:As an undergraduate he placed among the top five competitors in the William Lowell Putnam Competition on four occasions , a feat matched by only six other undergraduate students since the first competition in 1938...
, and Taylor.
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 numberGraph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
χ(G), and maximum degree
Glossary of graph theory
Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....
Δ(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.
- ch(G) ≤ χ(G) ln(n).
- ch(G) ≤ Δ(G) + 1.
- ch(G) ≤ 5 if G is a planar graphPlanar graphIn graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
. - ch(G) ≤ 3 if G is a bipartiteBipartite graphIn the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
planar graph.
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
.
It is known that k-choosability in bipartite graphs is
-complete for any k ≥ 3, and the same applies for 4-choosability in planar graphs, 3-choosability in planar triangle-free graphTriangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
s, and (2,3)-choosability in bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
planar graphs. For P5-free graphs, that is, graphs excluding a 5-vertex path graph
Path graph
In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
, k-choosability is fixed-parameter tractable.