A 3-coloring suits this graph, but fewer colors would result in adjacent vertices of the same color. Finding the minimum number of colors for an arbitrary graph is NP-hard. NP-hard (nondeterministic Polynomial-time hard in Computational complexity theory, is a class of problems informally "at least as hard as the hardest problems

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 Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects In the Mathematical discipline of Graph theory, a graph labeling is the assignment of labels traditionally represented with Integers to the edges In Mathematics and Computer science, a graph is the basic object of study in Graph theory. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges share the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Vertex coloring is the starting point of the subject, and other coloring problems can be transformed into a vertex version. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a planar graph is just a vertex coloring of its planar dual. In a Graph theory, the line graph L ( G) of an Undirected graph G is another graph L ( G) that represents the Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden In Mathematics, a dual graph of a given Planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge However, non-vertex coloring problems are often stated and studied as is. That is partly for perspective, and partly because some problems are best studied in non-vertex form, as for instance is edge coloring.

The convention of using colors originates from coloring the countries of a map, where each face is literally colored. This was generalized to coloring the faces of a graph embedded in the plane. In Topological graph theory, an embedding of a graph G on a Surface &Sigma is a representation of G on &Sigma in which points By planar duality it became coloring the vertices, and in this form it generalizes to all graphs. In mathematical and computer representations it is typical to use the first few positive or nonnegative integers as the "colors". In general one can use any finite set as the "color set". The nature of the coloring problem depends on the number of colors but not on what they are.

Graph coloring 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 color is assigned, or even on the color itself. It has even reached popularity with the general public in the form of the popular number puzzle Sudoku. is a Logic -based number-placement Puzzle. The objective is to fill a 9×9 grid so that each column each row and each of the nine 3×3 boxes (also called blocks Graph coloring is still a very active field of research.

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

Vertex coloring

When used without any qualification, a coloring of a graph is always assumed to be a vertex coloring, namely an assignment of colors to the vertices of the graph. In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects Again, when used without any qualification, a coloring is nearly always assumed to be proper, meaning no two adjacent vertices are assigned the same color. Graph theory is a growing area in mathematical research and has a large specialized vocabulary Here, "adjacent" means sharing the same edge. In Mathematics and Computer science, a graph is the basic object of study in Graph theory. A coloring using at most k colors is called a (proper) k-coloring and is equivalent to the problem of partitioning the vertex set into k or fewer independent sets. In Graph theory, an independent set or stable set is a set of vertices in a graph no two of which are adjacent

The problem of coloring a graph has found a number of applications. Some of them are scheduling, register allocation in compilers, frequency assignment in mobile radios, and pattern matching. In Compiler optimization, register allocation is the process of Multiplexing a large number of target program Variables onto a small number of A compiler is a Computer program (or set of programs that translates text written in a computer language (the source language) into another This article is about professional equipment For mobile radios used in Amateur radio, see Amateur radio mobile operation. 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 colors needed to color a graph G is called its chromatic number, χ(G). 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. In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an A graph that can be assigned a (proper) k-coloring is k-colorable, and it is k-chromatic if its chromatic number is exactly k.

The problem of finding the chromatic number is NP-hard. NP-hard (nondeterministic Polynomial-time hard in Computational complexity theory, is a class of problems informally "at least as hard as the hardest problems The corresponding decision problem (Is there a coloring which uses at most k colors?) is NP-complete, and in fact was one of Karp's 21 NP-complete problems. In Computability theory and Computational complexity theory, a decision problem is a question in some Formal system with a yes-or-no answer depending on In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties One of the most important results in Computational complexity theory was Stephen Cook 's 1971 demonstration of the first (practically relevant NP-complete problem It remains NP-complete even on planar graphs of degree at most 4, as shown by Garey and Johnson in 1974^[1]. There are however some efficient approximation algorithms that employ semidefinite programming. Semidefinite programming ( SDP) is a subfield of Convex optimization concerned with the optimization of a linear objective function over the intersection of the cone

Some properties of χ(G):

1. χ(G) = 1 if and only if G is totally disconnected, i. Graph theory is a growing area in mathematical research and has a large specialized vocabulary e. , it has no edges.
2. χ(G) ≥ 3 if and only if G has an odd cycle (equivalently, if G is not bipartite). In Graph theory, a cycle graph is a graph that consists of a single cycle, or in other words some number of vertices connected in a closed chain In the mathematical field of Graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two
3. χ(G) ≥ ω(G), the clique number, i. Graph theory is a growing area in mathematical research and has a large specialized vocabulary e. , the number of vertices of a largest clique in G. In Graph theory, a clique in an Undirected graph G is a set of vertices V such that for every two vertices in V there exists an edge connecting
4. χ(G) ≤ Δ(G) + 1, 1 more than the maximum degree of a vertex. Graph theory is a growing area in mathematical research and has a large specialized vocabulary
5. χ(G) ≤ Δ(G) for a connected, simple graph G, unless G is a complete graph or an odd cycle (Brooks' theorem). In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an
6. χ(G) ≤ 4, for any planar graph G. Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden This famous result, called the four-color theorem, was stated by Augustus De Morgan in 1852, but remained unproven until 1976, when it was established by Kenneth Appel and Wolfgang Haken. The four color theorem (also known as the four color map theorem) states that given any plane separated into regions such as a political map of the states of a country Augustus De Morgan ( 27 June, 1806 &ndash 18 March, 1871) was a British Mathematician and Logician. 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

For planar graphs, vertex colorings are essentially dual to nowhere-zero flows.

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

If all finite subgraphs of an infinite graph G are k-colorable, then so is G. Graph theory is a growing area in mathematical research and has a large specialized vocabulary (de Bruijn and Erdős 1951)

The chromatic number of the plane, where two points are adjacent if they have unit distance, is unknown, although it is one of 4, 5, 6, or 7. In Geometric graph theory, the Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance Other open problems concerning the chromatic number of graphs include the Hadwiger conjecture stating that every graph with chromatic number k has a complete graph on k vertices as a minor, and the Erdős–Faber–Lovász conjecture bounding the chromatic number of unions of complete graphs that have at exactly one vertex in common to each pair. This article lists some unsolved problems in Mathematics. See individual articles for details and sources In Graph theory, the Hadwiger conjecture (or Hadwiger's conjecture) states that if an Undirected graph G requires k or more colors In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an In Graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge In Graph theory, the Erdős–Faber–Lovász conjecture (1972 is a very deep problem about the coloring of graphs named after Paul Erdős, Vance

Algorithmic aspects

Optimal coloring

Vertex coloring in the general case is an NP-Complete problem. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties Instead of asking for the smallest number of colors needed to color the graph, we can ask easier questions of the form "Can we color the graph with at most k colors?"

The case k = 2 is equivalent to determining whether or not the graph is bipartite. In the mathematical field of Graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two This can be accomplished in polynomial time. For k >= 3 the problem is NP-Complete. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties 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. See also Gap theorem (disambiguation for other gap theorems in Mathematics.

One consequence of the Strong Perfect Graph Theorem of Chudnovsky, Robertson, Seymour, and Thomas is that it is possible to determine the chromatic number of a perfect graph in polynomial time. In Graph theory, a perfect graph is a graph in which the chromatic number of every Induced subgraph equals the clique number of that

Existing algorithms

The coloring algorithms can be divided into two categories:

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

- The algorithms that do not ensure a result with the smallest possible number of colors. Here we can find the sequential algorithms (those that color one vertex at a time), heuristic algorithms, global randomized algorithms, metaheuristic algorithms (using simulated annealing, tabu search, etc. 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 Simulated annealing (SA is a generic probabilistic Meta-algorithm for the Global optimization problem namely locating a good approximation to the Tabu search is a mathematical optimization method belonging to the class of local search techniques ), and genetic algorithms, to name several types. A genetic algorithm (GA is a Search technique used in Computing to find exact or Approximate solutions to optimization and Search

Algorithm of Welsh and Powell

The Welsh-Powell algorithm^[2] for coloring a graph uses a simple heuristic improvement to a completely naive greedy algorithm. By processing the vertices in non-increasing order of degree, that is, ordering them so that , where d_i is the degree of the ith node, this algorithm uses α(G) colors where

The algorithm is as follows:

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

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

Chromatic polynomial

This graph can be 3-colored 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 colors, the graph in the image to the right can be colored in 12 ways. With only two colors, it cannot be colored at all. With four colors, it can be colored in 24 + 4⋅12 = 72 ways: using all four colors, there are 4! = 24 valid colorings (every assignment of four colors to any 4-vertex graph is a proper coloring); and for every choice of three of the four colors, there are 12 valid 3-colorings. So, for the graph in the example, a table of the number of valid colorings would start like this:

The chromatic polynomial is a function P(G,t) that counts the number of t-colorings of G. As the name indicates, for a given G the function is indeed a polynomial in t. In Mathematics, a polynomial is an expression constructed from Variables (also known as indeterminates and Constants using the operations For the example graph, P(G,t) = t(t − 1)²(t − 2), and indeed P(G,4) = 72.

The chromatic polynomial includes at least as much information about the colorability 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. George David Birkhoff ( 21 March 1884, Overisel Michigan - 12 November 1944, Cambridge Massachusetts) was an American The four color theorem (also known as the four color map theorem) states that given any plane separated into regions such as a political map of the states of a country It remains an unsolved problem to characterize graphs which have the same chromatic polynomial and to determine precisely which polynomials are chromatic.

Examples

The Petersen graph has chromatic number 3. In Graph theory, the Petersen graph is an Undirected graph with 10 vertices and 15 edges

Chromatic polynomials for certain graphs

Triangle K3	t(t − 1)(t − 2)
Complete graph Kn
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)

Properties

• P(G,0) = 0
• P(G,1) = 0 if G contains an edge
• P(G,t) = 0, if t < χ(G). In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an In Graph theory, a tree is a graph in which any two vertices are connected by exactly one path. In Graph theory, a cycle graph is a graph that consists of a single cycle, or in other words some number of vertices connected in a closed chain In Graph theory, the Petersen graph is an Undirected graph with 10 vertices and 15 edges
• ( − 1) ^{| V(G) |} P(G, − 1) is the number of acyclic orientations of G^[3]
• If G has n vertices, m edges, and k components G₁,G₂,…,G_k, then
  • P(G,t) has degree n. In an Undirected graph, a connected component or component is a maximal connected subgraph
  • The coefficient of tⁿ in P(G,t) is 1.
  • The coefficient of t^{n − 1} in P(G,t) is − m.
  • The coefficients of are all zero.
  • The coefficient of t^k is nonzero.
  • 
• 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

Computing the chromatic polynomial

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

P(G,t) = 0.

If e is not a loop, then the chromatic polynomial satisfies the recurrence relation:

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. "Difference equation" redirects here It should not be confused with a Differential equation.

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, 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. #P-complete, pronounced "sharp P complete" or "number P complete" is a complexity class in complexity theory.

Other types of colorings

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

Some improper colorings:

Generalizations

Coloring can be considered for signed graphs and gain graphs. In Graph theory, edge coloring is one type of the Graph coloring problem 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 In Mathematics, list edge-coloring is a type of Graph coloring. In Graph theory, total coloring is a type of coloring on the vertices and edges of a graph In Graph theory, a harmonious coloring is a (proper vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices In Graph theory, complete coloring is the opposite of Harmonious coloring in the sense that it is a vertex coloring in which every pair of colors appears In Graph theory, an exact coloring is a (proper vertex coloring in which every pair of colors appears on exactly one pair of adjacent vertices In Graph theory, an acyclic coloring is a (proper vertex coloring in which every 2-chromatic subgraph is acyclic. In Graph theory, a strong coloring, with respect to a partition of the vertices into (disjoint subsets of equal sizes is a (proper vertex coloring in which In Graph theory, path coloring usually refers to one of two problems The problem of coloring a (multiset of paths R in graph Fractional coloring is a topic in a young branch of Graph theory known as Fractional graph theory. In Graph theory, oriented graph coloring is a special type of Graph coloring. In Graph theory, a cocoloring of a graph G is an assignment of colors to the vertices such that each color class forms an independent set in G In Graph theory, a subcoloring is an assignment of Colors to a graph 's vertices such that each color class induces a vertex disjoint union In the area of Graph theory in Mathematics, a signed graph is a graph in which each edge has a positive or negative sign Similar questions arise.

References

Literature

• R. L. Brooks (1941). "On colouring the nodes of a network". Proc. Cambridge Phil. Soc. 37: 194–197.  
• N. G. de Bruijn & P. Erdős (1951), “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Nicolaas Govert de Bruijn (born 9 July, 1918) is a Dutch Mathematician, affiliated as Professor emeritus Paul Erdős ( Hungarian: Erdős Pál, in English occasionally Paul Erdos or Paul Erdös, March 26, 1913 &ndash Akad. Wetensch. Proc. Ser. A 54: 371–373  (= Indag. Math. 13)
• Tommy R. Jensen and Bjarne Toft (1995), Graph Coloring Problems, Wiley-Interscience, New York, ISBN 0-471-02865-7 
• Marek Kubale et al. (2004). Graph Colorings. American Mathematical Society. ISBN 0-8218-3458-4.  
• Michael R. Garey, David S. Johnson, and L. Michael R Garey is a Computer science researcher and co-author (with David S David Stifler Johnson (born December 9, 1945) is a Computer scientist specializing in Algorithms and optimization 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). Michael R Garey is a Computer science researcher and co-author (with David S David Stifler Johnson (born December 9, 1945) is a Computer scientist specializing in Algorithms and optimization Computers and Intractability: A Guide to the Theory of NP-Completeness. Computers and Intractability A Guide to the Theory of NP-Completeness is a Computational complexity theory textbook by Michael Garey and David S W. H. Freeman. ISBN 0-7167-1045-5.   A1. 1: GT4, pg. 191.
• West, Douglas B. (1996). Introduction to Graph Theory. Prentice-Hall. ISBN 0-13-227828-6.  

See also

• Uniquely colorable graph
• Critical graph
• Graph homomorphism
• Sudoku

External links

• Chromatic number of a space at PlanetMath. 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 is a Logic -based number-placement Puzzle. The objective is to fill a 9×9 grid so that each column each row and each of the nine 3×3 boxes (also called blocks 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