Image:3colouringEx.svg A 3colouring 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 NPhard. 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, NPhard (Nondeterministic Polynomialtime 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 polynomialtime manyone 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, nonvertex 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. ...
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) kcolouring 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 multilanguage, multitarget 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 K_{n} of n vertices (a graph with an edge between every two vertices), is χ(K_{n}) = n. A graph that can be assigned a (proper) kcolouring is kcolourable, and it is kchromatic 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 NPhard. The corresponding decision problem (is there a colouring which uses at most k colors?) is NPcomplete, and in fact was one of Karp's 21 NPcomplete problems. It remains NPcomplete 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, NPhard (Nondeterministic Polynomialtime 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 polynomialtime manyone 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 yesorno answer. ...
In complexity theory, the NPcomplete 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 NPcomplete 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 NPcomplete 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):  χ(G) = 1 if and only if G is totally disconnected.
 χ(G) ≥ 3 if and only if G has an odd cycle (equivalently, if G is not bipartite).
 χ(G) ≥ ω(G).
 χ(G) ≤ Δ(G)+1.
 χ(G) ≤ Δ(G) for connected G, unless G is a complete graph or an odd cycle (Brooks' theorem).
 χ(G) ≤ 4, for any planar graph G. This famos result, called the fourcolour 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 UrbanaChampaign.
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 endpoints 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 (18611955) 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 UrbanaChampaign, solved one of the most famous problems in mathematics, the fourcolor theorem. ...
Wolfgang Haken (born June 21, 1928) is a mathematician who specialized in topology, in particular 3manifolds. ...
The University of Illinois at UrbanaChampaign (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 kcolourable, then so is G. (de Bruijn, Erdős 1951)
For planar graphs, vertex colouring is dual to nowherezero 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, nowherezero 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 NPComplete 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 NPcomplete 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 NPcomplete 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 NPComplete. 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 NPcomplete 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 NPcomplete 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 blackbox procedures â€” usually heuristics themselves â€” in a hopefully efficient way. ...
Simulated annealing (SA) is a generic probabilistic metaalgorithm 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 difficulttosolve problems through application of the principles of evolutionary biology to computer science. ...
Algorithm of Welsh and Powell The WelshPowell 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:  Sort the vertices in decreasing order of degree and initially have every vertex uncoloured.
 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.
 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 3coloured 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 4vertex graph is a proper colouring); and for every choice of three of the four colours, there are 12 valid 3colourings. 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_threecolourings. ...
Image File history File links Graph_with_all_threecolourings. ...
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 tcolourings 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 fourcolor 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 Chromatic polynomials for certain graphs Triangle K_{3}  t(t − 1)(t − 2)  Complete graph K_{n}  t(t − 1)(t − 2)...(t − n + 1)  Tree with n vertices  t(t − 1)^{n − 1}  Cycle C_{n}  (t − 1)^{n} + ( − 1)^{n}(t − 1)  Petersen graph  t(t − 1)(t − 2)(t^{7} − 12t^{6} + 67t^{5} − 230t^{4} + 529t^{3} − 814t^{2} + 775t − 352)  Image File history File links Petersen_graph_3coloring. ...
Image File history File links Petersen_graph_3coloring. ...
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 G_{1},G_{2},…,G_{k}, then
 P(G,t) has degree n.
 The coefficient of t^{n} in P(G,t) is 1.
 The coefficient of t^{n − 1} in P(G,t) is − m.
 The coefficients of t^{0},t^{1}, … t^{k − 1} are all zero.
 The coefficient of t^{k} is nonzero.
 P(G,t) = P(G_{1},t)P(G_{2},t)⋯P(G_{k},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(G − e,t) − P(G / e,t)
where G − e 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 2^{m}, where m is the number of edges. The analysis can be improved to 1.62^{n + m}. Other algorithms are known, but all are exponential in the size of the graph. For some classes of graphs, polynomialtime algorithms are known. These include the empty and complete graphs, forests, chordal graphs, wheels, and ladders. In general, computing the chromatic polynomial is #Pcomplete, 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 edgecolouring  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 2chromatic 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)  Online 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  Sumcolouring  The criterion of minimalization is the sum of colours  Tcolouring  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 edgecolouring  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  ^ * M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NPcomplete problems. Proceedings of the sixth annual ACM symposium on Theory of computing, p.4763. 1974.
 ^ 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, WileyInterscience, New York, ISBN 0471028657
 Marek Kubale and others (2004). Graph Colorings. American Mathematical Society. ISBN 0821834584.
 Michael R. Garey, David S. Johnson, and L. Stockmeyer (1974). "Some simplified NPcomplete problems". Proceedings of the sixth annual ACM symposium on Theory of computing: 4763.
 Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman. ISBN 0716710455. 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) Hungarianborn mathematician. ...
Michael R. Garey is a computer science researcher, and coauthor (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NPcompleteness. ...
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 coauthor (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NPcompleteness. ...
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 Commonslogo. ...
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 kchromatic graph that has only one possible (proper) kcoloring 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
 GFGraph Coloring Program [1]
 Links to Graph Coloring source codes
