FACTOID # 25: If you're tired of sitting in traffic on your way to work, move to North Dakota.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Graph coloring
Image:3-colouringEx.svg
A 3-colouring suits this graph, but fewer colours would result in adjacent vertices of the same colour. Finding the minimum number of colours for an arbitrary graph is NP-hard.

In graph theory, graph colouring is an assignment of "colours" to certain objects in 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 same colour, called a vertex colouring. Similarly, an edge colouring assigns a colour to each edge so that no two incident edges share the same colour, and a face colouring of a planar graph assigns a colour to each face or region so that no two faces that share a boundary share the same colour. In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... A pictorial representation of a graph 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. ...


Vertex colouring is the starting point of the subject, and other colouring problems can be transformed into a vertex version. For example, an edge colouring of a graph is just the vertex colouring of its line graph, and a face coloring of a planar graph is just the vertex colouring of its (planar) dual. However, to keep things in their perspective, non-vertex colouring problems are usually stated and studied as are. In graph theory, the line graph L(G) of a graph G is a graph such that each node of L(G) represents an edge of G; and any two nodes of L(G) are adjacent if and only if their corresponding edges are incident, meaning they share a common... In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... G′is the dual graph of G Dual graph is a term used in the mathematical study of graphs. ...


The convention of using colours comes from graph drawings of graph colourings, where each node or edge is literally coloured to indicate its mapping. In computer representations it's more typical to use nonnegative integers, and in general any mapping from the graph objects into a finite set can be used.


Graph colouring is not to be confused with graph labeling, which is an assignment of labels, usually also in the form of numbers, to vertices or edges. In graph colouring problems, colours (e.g. 1, 2, 3...) are nothing more than markers for keeping track of adjacency or incidence. In graph labeling problems, labels (e.g. 1, 2, 3...) are calculable values that need to satisfy a certain numerical condition in the definition of the labeling. In the mathematical discipline of graph theory, a graph labeling is the assignment of unique identifiers to the edges and vertices of a graph. ...


Graph colouring enjoys many practical applications as well as theoretical challenges. Beside the classical types of problems, different limitations can also be set on the graph, or on the way a colour is assigned, or even on the colour itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. Graph colouring is still a very active field of research. A sudoku puzzle. ...


Note: Many terms used in this article are defined in the glossary of graph theory. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ...

Contents

Vertex colouring

When used without any qualification, a colouring of a graph is always assumed to be a vertex colouring, namely an assignment of colours to the vertices of the graph. Again, when used without any qualification, a colouring is nearly always assumed to be proper, meaning no two adjacent vertices are assigned the same colour. Here, "adjacent" means sharing the same edge. A colouring using at most k colours is called a (proper) k-colouring and is equivalent to the problem of partitioning the vertex set into k or fewer independent sets. The problem of colouring a graph has found a number of applications such as scheduling, register allocation in compilers, frequency assignment in Mobile radios, and pattern matching. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... This article just presents the basic definitions. ... In graph theory, an independent, or stable, set in a graph G, which contains vertices V, is a set of vertices V (a subset of V) such that for every two vertices in V, there is no edge connecting the two. ... For schedule in computer science, see schedule (computer science). ... In computer architecture, a processor register is a small amount of very fast computer memory used to speed the execution of computer programs by providing quick access to commonly used values—typically, the values being in the midst of a calculation at a given point in time. ... A diagram of the operation of a typical multi-language, multi-target compiler. ... This article is about professional equipment. ... In computer science, pattern matching is the act of checking for the presence of the constituents of a given pattern. ...


Chromatic number

The least number of colours needed to colour the graph is called its chromatic number χ. For example the chromatic number of a complete graph Kn of n vertices (a graph with an edge between every two vertices), is χ(Kn) = n. A graph that can be assigned a (proper) k-colouring is k-colourable, and it is k-chromatic if its chromatic number is exactly k. Look up Χ, χ in Wiktionary, the free dictionary. ... In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ...


The problem of finding a minimum colouring of a graph is NP-hard. The corresponding decision problem (is there a colouring which uses at most k colors?) is NP-complete, and in fact was one of Karp's 21 NP-complete problems. It remains NP-complete even on planar graphs of degree at most 4, as shown by Garey and Johnson in 1974[1], although on planar graphs it's trivial for k > 3 (due to the four colour theorem). There are however some efficient approximation algorithms that employ semidefinite programming. In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... One of the most important results of computational complexity theory was Stephen Cooks 1971 paper that demonstrated the first NP-complete problem, the boolean satisfiability problem. ... Example of a four color map The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same colour. ... Semidefinite programming (SDP) is an area of mathematics concerned with special optimization problems: the optimization of a linear objective function over the intersection of the cone of positive semidefinite matricies with an affine space. ...


Some properties of χ(G):

  1. χ(G) = 1 if and only if G is totally disconnected.
  2. χ(G) ≥ 3 if and only if G has an odd cycle (equivalently, if G is not bipartite).
  3. χ(G) ≥ ω(G).
  4. χ(G) ≤ Δ(G)+1.
  5. χ(G) ≤ Δ(G) for connected G, unless G is a complete graph or an odd cycle (Brooks' theorem).
  6. χ(G) ≤ 4, for any planar graph G. This famos result, called the four-colour theorem, was stated by P. J. Heawood in 1890 (first written reference by Augustus De Morgan in 1852), but remained unproven until 1976, when it was established by Kenneth Appel and Wolfgang Haken at the University of Illinois at Urbana-Champaign.

Here Δ(G) is the maximum degree, and ω(G), the clique number. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ... In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjoint sets and such that no edge has both end-points in the same set. ... In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... Example of a four color map The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same colour. ... Percy John Heawood (1861-1955) was a British mathematician. ... The tone or style of this article or section may not be appropriate for Wikipedia. ... Kenneth Appel (born 1932) is a mathematician who, in 1976 with colleague Wolfgang Haken at the University of Illinois at Urbana-Champaign, solved one of the most famous problems in mathematics, the four-color theorem. ... Wolfgang Haken (born June 21, 1928) is a mathematician who specialized in topology, in particular 3-manifolds. ... The University of Illinois at Urbana-Champaign (UIUC), is the largest campus in the University of Illinois system. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ...


About infinite graphs, much less is known. The following is one of the few results about infinite graph colouring:

If all finite subgraphs of an infinite graph G are k-colourable, then so is G. (de Bruijn, Erdős 1951)

For planar graphs, vertex colouring is dual to nowhere-zero flows. The chromatic number of the plane is still unknown, although it is believed that is must be one of 4, 5, 6, or 7. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... In graph theory, nowhere-zero flows are a special type of network flow which is related (by duality) to coloring planar graphs. ...


Algorithmic aspects

Optimal colouring

Vertex colouring in the general case is an NP-Complete problem. Instead of asking for the smallest number of colours needed to colour the graph, we can ask easier questions of the form "Can we colour the graph with at most k colours?" In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...


The case k = 2 is equivalent to determining whether or not the graph is bipartite. This can be accomplished in polynomial time. For k >= 3 the problem is NP-Complete. By the gap theorem, this implies that the problem can not be approximated by a polynomial algorithm within a factor of 4/3 unless P=NP. In the mathematical field of graph theory, a bipartite graph is a special graph where the set of vertices can be divided into two disjunct sets with two vertices of the same set never sharing an edge. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In computational complexity theory the Gap theorem is an important theorem about the complexity of computable functions. ...


There is a remarkable result by László Lovász stating that it is possible to tell the chromatic number of a perfect graph in polynomial time. László Lovász (1948-) is a Hungarian mathematician, known for work in combinatorics, for which he was in 1999 awarded a Wolf Prize. ... In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph. ...


Existing algorithms

The colouring algorithms can be divided into two categories:


- The optimal colouring algorithms (for example the algorithm of Zykov, the method of branch and bound, etc.). Branch and bound is a general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. ...


- The algorithms that do not ensure a result with the smallest possible number of colours. Here we can find the sequential algorithms (those that colour one vertex at a time), heuristic algorithms, global randomized algorithms, metaheuristic algorithms (using simulated annealing, tabu search, etc.), and genetic algorithms, to name several types. A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. ... A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user given black-box procedures — usually heuristics themselves — in a hopefully efficient way. ... Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. ... Tabu search is a mathematical optimization method, belonging to the class of local search techniques. ... A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ...


Algorithm of Welsh and Powell

The Welsh-Powell algorithm for colouring a graph uses a simple heuristic improvement to a completely naive greedy algorithm. It is easy to show that this approach uses at most Δ(G) + 1 colours, where Δ(G) is the maximum degree of the graph. The algorithm is as follows:

  1. Sort the vertices in decreasing order of degree and initially have every vertex uncoloured.
  2. Traverse the vertices in order, giving a vertex colour 1 if it is uncoloured and it does not yet have a neighbour with colour 1.
  3. Repeat this process with colours 2, 3, etc. until no vertex is uncoloured.

This algorithm does not necessarily find a χ(G) colouring.


Chromatic polynomial

This graph can be 3-coloured in 12 different ways.
This graph can be 3-coloured in 12 different ways.

The chromatic polynomial counts the number of ways a graph can be colored using no more than a given number of colors. For example, using three colours, the graph in the image to the right can be coloured in 12 ways. With only two colours, it cannot be coloured at all. With four colours, it can be coloured in 24 + 4⋅12 = 72 ways: using all four colours, there are 4! = 24 valid colourings (every assignment of four colours to any 4-vertex graph is a proper colouring); and for every choice of three of the four colours, there are 12 valid 3-colourings. So, for the graph in the example, a table of the number of valid colourings would start like this: Image File history File links Graph_with_all_three-colourings. ... Image File history File links Graph_with_all_three-colourings. ...

Available colours 1 2 3 4
Number of colourings 0 0 12 72

The chromatic polynomial is a function P(G,t) that counts the number of t-colourings of G. As the name indicates, for a given G the function is indeed a polynomial in t. For the example graph, P(G,t) = t(t − 1)2(t − 2), and indeed P(G,4) = 72. In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ...


The chromatic polynomial includes at least as much information about the colourability of G as does the chromatic number. Indeed, χ is the smallest positive integer that is not a root of the chromatic polynomial,

χ(G) = min{k:P(G,k) > 0}

It was first used by Birkhoff and Lewis in their attack on the four-color theorem. It remains an unsolved problem to characterize graphs which have the same chromatic polynomial and to determine precisely which polynomials are chromatic. George David Birkhoff George David Birkhoff (21 March 1884, Overisel, Michigan - 12 November 1944, Cambridge, Massachusetts) was an American mathematician, best known for what is now called the ergodic theorem. ... Example of a four color map The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same colour. ...


Examples

The Petersen graph has chromatic number 3.
The Petersen graph has chromatic number 3.
Chromatic polynomials for certain graphs
Triangle K3 t(t − 1)(t − 2)
Complete graph Kn t(t − 1)(t − 2)...(tn + 1)
Tree with n vertices t(t − 1)n − 1
Cycle Cn (t − 1)n + ( − 1)n(t − 1)
Petersen graph t(t − 1)(t − 2)(t7 − 12t6 + 67t5 − 230t4 + 529t3 − 814t2 + 775t − 352)

Image File history File links Petersen_graph_3-coloring. ... Image File history File links Petersen_graph_3-coloring. ... The Petersen graph has crossing number 2. ... In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. ... A tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ... In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ... The Petersen graph has crossing number 2. ...

Properties

  • P(G,0) = 0
  • P(G,1) = 0 if G contains an edge
  • P(G,t) = 0, if t < χ(G).
  • P(G, − 1) is the number of acyclic orientations of G[2]
  • If G has n vertices, m edges, and k components G1,G2,…,Gk, then
    • P(G,t) has degree n.
    • The coefficient of tn in P(G,t) is 1.
    • The coefficient of tn − 1 in P(G,t) is m.
    • The coefficients of t0,t1,tk − 1 are all zero.
    • The coefficient of tk is nonzero.
    • P(G,t) = P(G1,t)P(G2,t)P(Gk,t)
  • The coefficients of every chromatic polynomial alternate in signs.
  • A graph G with n vertices is a tree if and only if P(G,t) = t(t − 1)n − 1.
  • The derivative evaluated at unity, P'(G,1) is the chromatic invariant θ(G) up to sign

In an undirected graph, a connected component or component is a maximal connected subgraph. ...

Computing the chromatic polynomial

Whenever G contains a loop, it cannot be legally coloured at all, so:

P(G,t) = 0.

If e is not a loop, then the chromatic polynomial satisfies the recurrence relation: In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

P(G,t) = P(Ge,t) − P(G / e,t)

where Ge is the graph with the edge removed, and G / e is the graph with the edge's endpoints contracted into a single vertex.


The two expressions give rise to a recursive procedure, called the deletion–contraction algorithm. In the recursive step, the instance is transformed into two instances that are at least one edge smaller, so the running time comes within a polynomial factor of 2m, where m is the number of edges. The analysis can be improved to 1.62n + m.


Other algorithms are known, but all are exponential in the size of the graph. For some classes of graphs, polynomial-time algorithms are known. These include the empty and complete graphs, forests, chordal graphs, wheels, and ladders. In general, computing the chromatic polynomial is #P-complete, so it is unlikely that a polynomial time algorithm for all graphs will be found. The title given to this article is incorrect due to technical limitations. ...


Other types of colourings

Not only can the idea of vertex colouring be extended to edges, but also be added with different conditions to form new structures and problems.

Edge colouring Edges are coloured
List colouring Each vertex chooses from a list of colours
List edge-colouring Each edge chooses from a list of colours
Total colouring Vertices and edges are coloured
Harmonious colouring Every pair of colours appears on at most one edge
Complete colouring Every pair of colours appears on at least one edge
Exact colouring Every pair of colours appears on exactly one edge
Acyclic colouring Every 2-chromatic subgraph is acyclic
Strong colouring Every colour appears in every partition of equal size exactly once
Strong edge colouring Edges are coloured such that each colour class induces a matching (equivalent to colouring the square of the line graph)
On-line colouring The instance of the problem is not given in advance and its successive parts become known over time
Equitable colouring The sizes of colour classes differ by at most one
Sum-colouring The criterion of minimalization is the sum of colours
T-colouring Distance between two colours of adjacent vertices must not belong to fixed set T
Rank colouring If two vertices have the same colour i, then every path between them contain a vertex with colour greater than i
Interval edge-colouring A colour of edges meeting in a common vertex must be contiguous
Circular colouring Motivated by task systems in which production proceeds in a cyclic way
Path colouring Models a routing problem in graphs
Fractional colouring Vertices may have multiple colours, and on each edge the sum of the colour parts of each vertex is not greater than one
Oriented colouring Takes into account orientation of edges of the graph

Some improper colourings: In graph theory, a branch of mathematics, list coloring is a type of graph coloring. ...

Cocolouring Every colour class induces an independent set or a clique
Subcolouring Every colour class induces a union of cliques

References

  1. ^ * M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete problems. Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63. 1974.
  2. ^ Stanley, 1973

Literature

  • Brooks, R. L. (1941). "On colouring the nodes of a network". Proc. Cambridge Phil. Soc. 37: 194–197. 
  • de Bruijn, N. G. & P. Erdős (1951), "A colour problem for infinite graphs and a problem in the theory of relations", Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373 (Indag. Math. 13.)
  • Jensen, Tommy R. & Bjarne Toft (1995), Graph coloring problems, Wiley-Interscience, New York, ISBN 0-471-02865-7
  • Marek Kubale and others (2004). Graph Colorings. American Mathematical Society. ISBN 0-8218-3458-4. 
  • Michael R. Garey, David S. Johnson, and L. Stockmeyer (1974). "Some simplified NP-complete problems". Proceedings of the sixth annual ACM symposium on Theory of computing: 47-63. 
  • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A1.1: GT4, pg.191.

Paul Erdős, also Erdős Pál, in English Paul Erdos or Paul Erdös (March 26, 1913 – September 20, 1996), was an immensely prolific (and famously eccentric) Hungarian-born mathematician. ... Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ... Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ...

See also

Wikimedia Commons has media related to:

Image File history File links Commons-logo. ... Example of a four color map The four color theorem states that every possible geographical map can be colored with at most four colors in such a way that no two adjacent regions receive the same colour. ... In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. ... In general the notion of criticality can refer to any measure. ... In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. ... In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the clique number of that subgraph. ... Unsolved problems in mathematics: How many colors are needed to color the plane so that no two points at unit distance are the same color? In mathematics, more specifically in geometric graph theory, the Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such... A sudoku puzzle. ...

External links

  • Chromatic number of a space at PlanetMath.org
  • Graph Coloring Page by Joseph Culberson (graph coloring programs)
  • CoLoRaTiOn by Jim Andrews and Mike Fellows is a graph coloring puzzle
  • GF-Graph Coloring Program [1]
  • Links to Graph Coloring source codes

  Results from FactBites:
 
Coloring a Graph (291 words)
In graph coloring, the name of the game is to color the vertices using the fewest number of colors (the only restriction being that nodes joined by an edge cannot be colored with the same color).
The purpose of the applet is to develop the user's skill in finding optimal colorings (colorings that use the minimal number of colors), or at least "good" colorings of the nodes of a graph.
Coloring can be done either by picking a color from a checkbox at the bottom, or by cycling through the colors.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m