{
  "id": "enwiki-001373913102",
  "slug": "graph-coloring",
  "title": "Graph coloring",
  "qid": "",
  "lead": "with 3 colors, the minimum number possible. In graph theory, graph coloring is a methodic assignment of labels traditionally called \"colors\" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring is a special case of graph labeling. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of 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 are of 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 often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is partly pedagogical, and partly because some problems are best studied in their non-vertex form, as in the case of edge coloring. The convention of using colors originates from coloring the countries in a political map, where each face is literally colored.…",
  "body": "with 3 colors, the minimum number possible. In graph theory, graph coloring is a methodic assignment of labels traditionally called \"colors\" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring is a special case of graph labeling. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of 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 are of 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 often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is partly pedagogical, and partly because some problems are best studied in their non-vertex form, as in the case of edge coloring. The convention of using colors originates from coloring the countries in a political map, where each face is literally colored. This was generalized to coloring the faces of a graph embedded in the plane. 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 non-negative 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. Graph coloring is still a very active field of research. The chromatic polynomial counts the number of ways a graph can be colored using some of a given number of colors. For example, using three colors, the graph in the adjacent image 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 that counts the number of -colorings of . As the name indicates, for a given the function is indeed a polynomial in . For the example graph, , and indeed . The chromatic polynomial includes more information about the colorability of than does the chromatic number. Indeed, is the smallest positive integer that is not a zero of the chromatic polynomial . The only graphs that can be 1-colored are edgeless graphs. A complete graph K_n of n vertices requires \\chi(K_n)=n colors. In an optimal coloring there must be at least one of the graph's m edges between every pair of color classes, so \\chi(G)(\\chi(G)-1) \\le 2m. More generally a family \\mathcal{F} of graphs is -bounded if there is some function c such that the graphs G in \\mathcal{F} can be colored with at most c(\\omega(G)) colors, where \\omega(G) is the clique number of G . For the family of the perfect graphs this function is c(\\omega(G))=\\omega(G) . The 2-colorable graphs are exactly the bipartite graphs, including trees and forests. By the four color theorem, every planar graph can be 4-colored. A greedy coloring shows that every graph can be colored with one more color than the maximum vertex degree, \\chi(G) \\le \\Delta(G) + 1. Complete graphs have \\chi(G)=n and \\Delta(G)=n-1 , and odd cycles have \\chi(G)=3 and \\Delta(G)=2 , so for these graphs this bound is best possible. In all other cases, the bound can be slightly improved; Brooks' theorem states that Brooks' theorem: \\chi (G) \\le \\Delta (G) for a connected, simple graph G, unless G is a complete graph or an odd cycle. Hoffman's bound: Let W be a real symmetric matrix such that W_{i,j} = 0 whenever (i,j) is not an edge in G . Define \\chi_W(G) = 1 - \\tfrac{\\lambda_{\\max}(W)}{\\lambda_{\\min}(W)} , where \\lambda_{\\max}(W), \\lambda_{\\min}(W) are the largest and smallest eigenvalues of W . Define \\chi_H(G) = \\max_W \\chi_W(G) , with W as above. Then: \\chi_H(G)\\leq \\chi(G). : Let W be a positive semi-definite matrix such that W_{i,j} \\le -\\tfrac{1}{k-1} whenever (i,j) is an edge in G . Define \\chi_V(G) to be the least k for which such a matrix W exists. Then \\chi_V(G)\\leq \\chi(G). Lovász number: The Lovász number of a complementary graph is also a lower bound on the chromatic number: \\vartheta(\\bar{G}) \\leq \\chi(G). Fractional chromatic number: The fractional chromatic number of a graph is a lower bound on the chromatic number as well: \\chi_f(G) \\leq \\chi(G). These bounds are ordered as follows: \\chi_H(G) \\leq \\chi_V(G) \\leq \\vartheta(\\bar{G}) \\leq \\chi_f(G) \\leq \\chi(G). \\chi'(G)=\\chi(L(G)). There is a strong relationship between edge colorability and the graph's maximum degree \\Delta(G) . Since all edges incident to the same vertex need their own color, we have \\chi'(G) \\ge \\Delta(G). Moreover, Kőnig's theorem: \\chi'(G) = \\Delta(G) if G is bipartite. In general, the relationship is even stronger than what Brooks's theorem gives for vertex coloring: Vizing's Theorem: A graph of maximal degree \\Delta has edge-chromatic number \\Delta or \\Delta+1 . Brute-force search for a k-coloring considers each of the k^n assignments of k colors to n vertices and checks for each if it is legal. To compute the chromatic number and the chromatic polynomial, this procedure is used for every k=1,\\ldots,n-1 , impractical for all but the smallest input graphs. Using dynamic programming and a bound on the number of maximal independent sets, k-colorability can be decided in time and space O(2.4423^n) . Using the principle of inclusion–exclusion and Yates's algorithm for the fast zeta transform, k-colorability can be decided in time O(2^n n) for any k. Faster algorithms are known for 3- and 4-colorability, which can be decided in time O(1.3289^n) and O(1.7272^n) , respectively. Exponentially faster algorithms are also known for 5- and 6-colorability, as well as for restricted families of graphs, including sparse graphs. \\chi(G) = \\text{min} \\{ \\chi(G+uv), \\chi(G/uv)\\} due to , where u and v are non-adjacent vertices, and G+uv is the graph with the edge added. Several algorithms are based on evaluating this recurrence and the resulting computation tree is sometimes called a Zykov tree. The running time is based on a heuristic for choosing the vertices u and v. The chromatic polynomial satisfies the following recurrence relation P(G-uv, k)= P(G/uv, k)+ P(G, k), where u and v are adjacent vertices, and G-uv is the graph with the edge removed. P(G - uv, k) represents the number of possible proper colorings of the graph, where the vertices may have the same or different colors. Then the proper colorings arise from two different graphs. To explain, if the vertices u and v have different colors, then we might as well consider a graph where u and v are adjacent. If u and v have the same colors, we might as well consider a graph where u and v are contracted. Tutte's curiosity about which other graph properties satisfied this recurrence led him to discover a bivariate generalization of the chromatic polynomial, the Tutte polynomial. These expressions give rise to a recursive procedure called the deletion–contraction algorithm, which forms the basis of many algorithms for graph coloring. The running time satisfies the same recurrence relation as the Fibonacci numbers, so in the worst case the algorithm runs in time within a polynomial factor of \\left(\\tfrac{1+\\sqrt{5}}2\\right)^{n+m}=O(1.6180^{n+m}) for n vertices and m edges. The analysis can be improved to within a polynomial factor of the number t(G) of spanning trees of the input graph. In practice, branch and bound strategies and graph isomorphism rejection are employed to avoid some recursive calls. The running time depends on the heuristic used to pick the vertex pair. It is known that a -chromatic graph can be -colored in the deterministic LOCAL model, in O(n^{1/\\alpha}) . rounds, with \\alpha = \\left\\lfloor \\frac{c - 1}{\\chi - 1} \\right\\rfloor . A matching lower bound of \\Omega(n^{1/\\alpha}) rounds is also known. This lower bound holds even if quantum computers that can exchange quantum information, possibly with a pre-shared entangled state, are allowed. In the field of distributed algorithms, graph coloring is closely related to the problem of symmetry breaking. The current state-of-the-art randomized algorithms are faster for sufficiently large maximum degree Δ than deterministic algorithms. The fastest randomized algorithms employ the multi-trials technique by Schneider and Wattenhofer. In a symmetric graph, a deterministic distributed algorithm cannot find a proper vertex coloring. Some auxiliary information is needed in order to break symmetry. A standard assumption is that initially each node has a unique identifier, for example, from the set . Put otherwise, we assume that we are given an n-coloring. The challenge is to reduce the number of colors from n to, e.g., Δ + 1. The more colors are employed, e.g. O(Δ) instead of Δ + 1, the fewer communication rounds are required. A straightforward distributed version of the greedy algorithm for (Δ + 1)-coloring requires Θ(n) communication rounds in the worst case – information may need to be propagated from one side of the network to another side. The simplest interesting case is an n-cycle. Richard Cole and Uzi Vishkin show that there is a distributed algorithm that reduces the number of colors from n to O(log n) in one synchronous communication step. By iterating the same procedure, it is possible to obtain a 3-coloring of an n-cycle in O(  n) communication steps (assuming that we have unique node identifiers). The function , iterated logarithm, is an extremely slowly growing function, \"almost constant\". Hence the result by Cole and Vishkin raised the question of whether there is a constant-time distributed algorithm for 3-coloring an n-cycle. showed that this is not possible: any deterministic distributed algorithm requires Ω(  n) communication steps to reduce an n-coloring to a 3-coloring in an n-cycle. The technique by Cole and Vishkin can be applied in arbitrary bounded-degree graphs as well; the running time is poly(Δ) + O(  n). The technique was extended to unit disk graphs by Schneider and Wattenhofer. The fastest deterministic algorithms for (Δ + 1)-coloring for small Δ are due to Leonid Barenboim, Michael Elkin and Fabian Kuhn. The algorithm by Barenboim et al. runs in time O(Δ) +  (n)/2, which is optimal in terms of n since the constant factor 1/2 cannot be improved due to Linial's lower bound. use network decompositions to compute a Δ+1 coloring in time 2 ^{O\\left(\\sqrt{\\log n}\\right)} . The problem of edge coloring has also been studied in the distributed model. achieve a (2Δ − 1)-coloring in O(Δ +   n) time in this model. The lower bound for distributed vertex coloring due to applies to the distributed edge coloring problem as well. Computing the coefficients of the chromatic polynomial is #P-hard. In fact, even computing the value of \\chi(G,k) is #P-hard at any rational point k except for k = 1 and k = 2. There is no FPRAS for evaluating the chromatic polynomial at any rational point k ≥ 1.5 except for k = 2 unless NP = RP. For edge coloring, the proof of Vizing's result gives an algorithm that uses at most Δ+1 colors. However, deciding between the two candidate values for the edge chromatic number is NP-complete. In terms of approximation algorithms, Vizing's algorithm shows that the edge chromatic number can be approximated to within 4/3, and the hardness result shows that no (4/3 − ε)-algorithm exists for any ε > 0 unless P = NP. These are among the oldest results in the literature of approximation algorithms, even though neither paper makes explicit use of that notion. === Other applications=== The problem of coloring a graph arises in many practical areas such as sports scheduling, designing seating plans, exam timetabling, the scheduling of taxis, and solving Sudoku puzzles. \\sigma(v) = \\sum_{u \\in N(v)} c(u), where u is an arbitrary vertex in the neighborhood of v , N(v) . We then color each vertex with the new coloring determined by the sum of the adjacent vertices. The graph G has a modular k -coloring if, for every pair of adjacent vertices a and b , \\sigma(a) \\ne \\sigma(b) . The modular chromatic number of G , mc(G) , is the minimum value of k such that there exists a modular k -coloring of G . For example, let there be a vertex v adjacent to vertices with the assigned colors 0, 1, 1 , and 3 \\bmod 4 (that is, k=4 ). The color sum would be \\sigma(v) = (0 + 1 + 1 + 3) \\bmod 4 = 5 \\bmod 4 = 1 \\bmod{4} . This would be the new color of vertex v . We would repeat this process for every vertex in G . If none of the adjacent vertices have equal color sums, G has a modulo 4 coloring. (= Indag. Math. 13) . Translated into English in Amer. Math. Soc. Translation, 1952, .",
  "categories": [
    "23118434",
    "23374303",
    "23603337",
    "24623845",
    "28174277",
    "28269683",
    "29176239",
    "29176322",
    "29176365",
    "29265124",
    "48128016",
    "63706498",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1373913102",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1788883998.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001373913102",
    "type": "webpage",
    "title": "Graph coloring",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/graph-coloring",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001373913102",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1373913102",
    "note": "Immutable snapshot enwiki-001373913102"
  }
}