Graph coloring - Knowledge

494: 155: 334: 38: 5030: 5941:

vertex i.e., whether a local conflict exists. This is a mild assumption in many applications e.g. in wireless channel allocation it is usually reasonable to assume that a station will be able to detect whether other interfering transmitters are using the same channel (e.g. by measuring the SINR). This sensing information is sufficient to allow algorithms based on learning automata to find a proper graph coloring with probability one.

3807: 6347:, the complete graph of six vertices, there will be a monochromatic triangle; often illustrated by saying that any group of six people either has three mutual strangers or three mutual acquaintances. Ramsey theory is concerned with generalisations of this idea to seek regularity amid disorder, finding general conditions for the existence of monochromatic subgraphs with given structure. 529:

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

122:

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

5940:

is allowed (in contrast to distributed algorithms where local message passing takes places), and efficient decentralized algorithms exist that will color a graph if a proper coloring exists. These assume that a vertex is able to sense whether any of its neighbors are using the same color as the

6170:

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

5411:

establishes the ordering dynamically while the algorithm proceeds, choosing next the vertex adjacent to the largest number of different colors. Many other graph coloring heuristics are similarly based on greedy coloring for a specific static or dynamic strategy of ordering the vertices, these

2920:

is triangle-free and requires arbitrarily many colors to be properly colored. This family of graphs is then called the Burling graphs. The same class of graphs is used for the construction of a family of triangle-free line segments in the plane, given by Pawlik et al. (2014). It shows that the

6204:

in the sense that they may not be assigned to the same time slot, for example because they both rely on a shared resource. The corresponding graph contains a vertex for every job and an edge for every conflicting pair of jobs. The chromatic number of the graph is exactly the minimum

4137:

If the graph is planar and has low branch-width (or is nonplanar but with a known branch decomposition), then it can be solved in polynomial time using dynamic programming. In general, the time required is polynomial in the graph size, but exponential in the branch-width.

114:

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

238:. The proof went back to the ideas of Heawood and Kempe and largely disregarded the intervening developments. The proof of the four color theorem is noteworthy, aside from its solution of a century-old problem, for being the first major computer-aided proof. 961:

edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent vertices, no adjacent edges, and no edge and its end-vertices are assigned the same color. The total chromatic number

2822: 3594: 2082: 90:

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

5474:

of vertices in the graph using specialised heuristic rules. It then assigns these vertices to the same color and removes them from the graph. These actions are repeated on the remaining subgraph until no vertices remain.

4964: 538:

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:

5830:

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

229:

colors, using ideas of Kempe. In the following century, a vast amount of work was done and theories were developed to reduce the number of colors to four, until the four color theorem was finally proved in 1976 by

4828:

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

4578: 6084: 5458:

has been coloured, the algorithm determines which of the remaining uncoloured vertices has the highest number of different colours in its neighbourhood and colours this vertex next. This is defined as the

5405: 4628:

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

261:. Kempe had already drawn attention to the general, non-planar case in 1879, and many results on generalisations of planar graph coloring to surfaces of higher order followed in the early 20th century. 3509: 2140: 2628: 186:, noting that four colors were sufficient to color the map so that no regions sharing a common border received the same color. Guthrie's brother passed on the question to his mathematics teacher 5900: 7962: 3789:, their conjecture is still unresolved. It also remains an unsolved problem to characterize graphs which have the same chromatic polynomial and to determine which polynomials are chromatic. 2228: 3195: 2395: 5241:, adding a fresh color if needed. The quality of the resulting coloring depends on the chosen ordering. There exists an ordering that leads to a greedy coloring with the optimal number of 1283: 3108: 4738: 2694: 2560: 2305: 1565: 3256: 1861: 1490: 1775: 5690:

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

5675:. The current state-of-the-art randomized algorithms are faster for sufficiently large maximum degree Δ than deterministic algorithms. The fastest randomized algorithms employ the 1128: 8917: 8764:

Schneider, Johannes; Wattenhofer, Roger (2008), "A log-star distributed maximal independent set algorithm for growth-bounded graphs", in Bazzi, Rida A.; Patt-Shamir, Boaz (eds.),

8155: 6200:. In the cleanest form, a given set of jobs need to be assigned to time slots, each job requires one such slot. Jobs can be scheduled in any order, but pairs of jobs may be in 210:

published a paper that claimed to establish the result, and for a decade the four color problem was considered solved. For his accomplishment Kempe was elected a Fellow of the

4861:

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

2977: 2948: 2914: 1062: 8638:

Pawlik, A.; Kozik, J.; Krawczyk, T.; Lasoń, M.; Micek, P.; Trotter, W.; Walczak, B. (2014), "Triangle-free intersection graphs of line segments with large chromatic number",

4230: 5582: 2705: 1644: 1399: 1310: 1211: 4408: 4372: 4281: 4134:

for chromatic polynomials are known for many classes of graphs, such as forests, chordal graphs, cycles, wheels, and ladders, so these can be evaluated in polynomial time.

1437: 6285:

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

3787: 2483: 1718: 3746: 3714: 6130: 3140: 1683: 1603: 4826: 4332: 3339: 1937: 5512: 5268: 5239: 3313: 3293: 3682: 317:

from 1972, and at approximately the same time various exponential-time algorithms were developed based on backtracking and on the deletion-contraction recurrence of

6345: 5638: 5206: 5179: 5152: 5125: 5098: 4178: 2427: 1969: 1332: 1165: 8300: 5001: 4778: 4622: 4450: 3044: 5304: 5063: 4410:, respectively. Exponentially faster algorithms are also known for 5- and 6-colorability, as well as for restricted families of graphs, including sparse graphs. 3514: 5602: 5532: 2986:

From Brooks's theorem, graphs with high chromatic number must have high maximum degree. But colorability is not an entirely local phenomenon: A graph with high

2503: 2447: 2336: 2248: 2160: 1989: 1898: 1375: 1355: 6607: 277: 5419:

The maximum (worst) number of colors that can be obtained by the greedy algorithm, by using a vertex ordering chosen to maximize this number, is called the

6212:

Details of the scheduling problem define the structure of the graph. For example, when assigning aircraft to flights, the resulting conflict graph is an

1994: 7525: 9102: 2860: 4879: 8922: 5407:

colors, at most one more than the graph's maximum degree. This heuristic is sometimes called the Welsh–Powell algorithm. Another heuristic due to

9097: 6183:. These are among the oldest results in the literature of approximation algorithms, even though neither paper makes explicit use of that notion. 5321:, the greedy coloring algorithm can be used to find optimal colorings in polynomial time, by choosing the vertex ordering to be the reverse of a 3645:

When Birkhoff and Lewis introduced the chromatic polynomial in their attack on the four-color theorem, they conjectured that for planar graphs

5604:

is the number of edges in the graph. This produces much faster runs with sparse graphs. The overall complexity of RLF is slightly higher than

9039: 8766:

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, Toronto, Canada, August 18-21, 2008

6361: 5777:, is an extremely slowly growing function, "almost constant". Hence the result by Cole and Vishkin raised the question of whether there is a 5710:

to, e.g., Δ + 1. The more colors are employed, e.g. O(Δ) instead of Δ + 1, the fewer communication rounds are required.

5534:

is the number of vertices in the graph. The algorithm can also be implemented using a binary heap to store saturation degrees, operating in

4188:

vertices and checks for each if it is legal. To compute the chromatic number and the chromatic polynomial, this procedure is used for every

3408: 3367: 5965:∈ {0,1,2} . In particular, it is NP-hard to compute the chromatic number. The 3-coloring problem remains NP-complete even on 4-regular 8808:

Welsh, D. J. A.; Powell, M. B. (1967), "An upper bound for the chromatic number of a graph and its application to timetabling problems",

362:(i.e. a connection directly back to itself) could never be properly colored, it is understood that graphs in this context are loopless. 7686: 6316:, where the graph's edges are assigned to colors, and there is no restriction on the colors of incident edges. A simple example is the 6269:, where vertices are variables and an edge connects two vertices if they are needed at the same time. If the graph can be colored with 3627: 4493: 1002:

discovered that if the graph is k-face-colorable then G admits a nowhere-zero k-flow. The equivalence holds if the surface is sphere.

8740:

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, July 25–28, 2010

6026: 5339: 8879: 6554:

Sum of the distance between the vertices and the difference of their colors is greater than k+1, where k is a positive integer.

5717:) communication rounds in the worst case − information may need to be propagated from one side of the network to another side. 5033:

Two greedy colorings of the same graph using different vertex orders. The right example generalizes to 2-colorable graphs with

3449: 889:, meaning an assignment of colors to edges so that no vertex is incident to two edges of the same color. An edge coloring with 17: 5015:

rejection are employed to avoid some recursive calls. The running time depends on the heuristic used to pick the vertex pair.

4872:, which forms the basis of many algorithms for graph coloring. The running time satisfies the same recurrence relation as the 8902: 8781: 8755: 8564: 8419: 8391: 8317: 7944: 7646: 7395: 2087: 8153:

Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials",

8083: 5811:

The technique by Cole and Vishkin can be applied in arbitrary bounded-degree graphs as well; the running time is poly(Δ) +

4088: 307:

Graph coloring has been studied as an algorithmic problem since the early 1970s: the chromatic number problem (see section

7755:

Crescenzi, P.; Kann, V. (December 1998), "How to find the best approximation results — a follow-up to Garey and Johnson",

7569: 3205: 2577: 5857: 3630:

bounding the chromatic number of unions of complete graphs that have at most one vertex in common to each pair, and the

2921:

chromatic number of its intersection graph is arbitrarily large as well. Hence, this implies that axis aligned boxes in

3607: 5744:) in one synchronous communication step. By iterating the same procedure, it is possible to obtain a 3-coloring of an 8839: 8725: 8709: 8480: 8288: 8270: 8250: 8200: 8010: 7971: 7926: 7703: 6612:

Edges are colored such that each color class induces a matching (equivalent to coloring the square of the line graph)

6446:

Vertices may have multiple colors, and on each edge the sum of the color parts of each vertex is not greater than one

5467: 5436: 314: 145: 8704:

Sekine, Kyoko; Imai, Hiroshi; Tani, Seiichiro (1995), "Computing the Tutte polynomial of a graph of moderate size",

2341: 2165: 7368: 6382:

a coloring of the vertices where each color class contains a vertex that has a neighbor in all other color classes.

6317: 3603: 3384:

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

377:

are only used when the number of colors is small, and normally it is understood that the labels are drawn from the

9051: 8078: 1223: 8640: 7888: 119:

as the "color set". The nature of the coloring problem depends on the number of colors but not on what they are.

7787:

Dailey, D. P. (1980), "Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete",

6473: 4646: 3602:, where two points are adjacent if they have unit distance, is unknown, although it is one of 5, 6, or 7. Other 2645: 2511: 2256: 1520: 8939:

Zuckerman, D. (2007), "Linear degree extractors and the inapproximability of Max Clique and Chromatic Number",

8339: 7789: 7720:

Cole, R.; Vishkin, U. (1986), "Deterministic coin tossing with applications to optimal parallel list ranking",

3639: 3148: 460: 293: 103:, and partly because some problems are best studied in their non-vertex form, as in the case of edge coloring. 6265:

The textbook approach to this problem is to model it as a graph coloring problem. The compiler constructs an

5470:

operates in a different fashion by constructing each color class one at a time. It does this by identifying a

1819: 1442: 9087: 8941: 6262:. Ideally, values are assigned to registers so that they can all reside in the registers when they are used. 4102:

Determining if a graph can be colored with 2 colors is equivalent to determining whether or not the graph is

1736: 3052: 1813:

colors are needed to color that clique; in other words, the chromatic number is at least the clique number:

5322: 1720:, so for these graphs this bound is best possible. In all other cases, the bound can be slightly improved; 1089: 301: 297: 285: 62: 6663:

An improper vertex coloring where every non-isolated node has at least one neighbor with a different color

3212: 8925:(LIPIcs), vol. 198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 113:1–113:20, 8036: 6366:

A total coloring with the additional restriction that any two adjacent vertices have different color sets

5004: 3599: 2634: 203: 8734:

Schneider, Johannes; Wattenhofer, Roger (2010), "A new technique for distributed symmetry breaking", in

5713:

A straightforward distributed version of the greedy algorithm for (Δ + 1)-coloring requires Θ(

1022:

of the graph. The colors remain labeled; it is the graph that is unlabeled. There is an analogue of the

7746: 6019:

It is also NP-hard to color a 3-colorable graph with 5 colors, 4-colorable graph with 7 colours, and a

4419: 2879:

To prove this, both, Mycielski and Zykov, each gave a construction of an inductively defined family of

2817:{\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).} 1015: 87:

assigns a color to each face or region so that no two faces that share a boundary have the same color.

6620:

Absolute value of the difference between two colors of adjacent vertices must not belong to fixed set

2953: 2924: 2890: 1038: 9092: 8915:

Barrier for 5-Coloring and 6-Coloring", in Bansal, Nikhil; Merelli, Emanuela; Worrell, James (eds.),

8441: 8125: 7561: 7490: 7465: 7334: 5326: 4191: 191: 8455: 7617:

Bulín, J.; Krokhin, A.; Opršal, J. (2019), "Algebraic approach to promise constraint satisfaction",

5537: 3266:

In general, the relationship is even stronger than what Brooks's theorem gives for vertex coloring:

1608: 1380: 1291: 1174: 8544: 8499: 6722: 4377: 4341: 4250: 4127: 2840:

is an example of a 4-chromatic graph without a triangle, and the example can be generalized to the

1404: 354:, namely a labeling of the graph's vertices with colors such that no two vertices sharing the same 132: 9036: 8103:

Halldórsson, M. M. (1993), "A still better performance guarantee for approximate graph coloring",

7664:

Byskov, J.M. (2004), "Enumerating maximal independent sets with applications to graph colouring",

7310: 3751: 2452: 1688: 9077: 7722: 6417: 5993: 5687: 5471: 4284: 4240: 3719: 3687: 901: 149: 8629:

Panconesi, A.; Srinivasan, A. (1996), "On the complexity of distributed network decomposition",

7921:; Gaspers, S.; Saurabh, S. (2007), "Improved exact algorithms for counting 3- and 4-colorings", 6100: 3116: 2990:

looks locally like a tree, because all cycles are long, but its chromatic number need not be 2:

1653: 1573: 8540: 8494: 8450: 6646: 6485: 6197: 5676: 4787: 4298: 4131: 3318: 1903: 258: 195: 7463:

Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), "Set partitioning via inclusion–exclusion",

5481: 5244: 493: 284:. The conjecture remained unresolved for 40 years, until it was established as the celebrated 110:, where each face is literally colored. This was generalized to coloring the faces of a graph 9082: 7425: 6712: 6251: 5668: 5455: 5447: 5333: 5211: 3298: 3278: 2833: 2639:

The fractional chromatic number of a graph is a lower bound on the chromatic number as well:

1802: 1511: 937: 242: 183: 66: 6707: 6250:

into another. To improve the execution time of the resulting code, one of the techniques of

3652: 3511:

A conjecture of Reed from 1998 is that the value is essentially closer to the lower bound,

8992: 8980: 8574: 8401: 8245:, The Art of Computer Programming, vol. 2 (3rd ed.), Reading/MA: Addison-Wesley, 8164: 7534: 7286: 6454:

Uses the length of the longest path between two vertices, also known as the detour distance

6449: 6323: 6217: 5611: 5451: 5184: 5157: 5130: 5103: 5076: 4156: 4111: 3631: 3589:{\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .} 2987: 2400: 1942: 1317: 1143: 1023: 520: 430: 246: 99:. However, non-vertex coloring problems are often stated and studied as-is. This is partly 9020: 7298: 6398:

An improper vertex coloring where every color class induces an independent set or a clique

4977: 4754: 4598: 4424: 3020: 2571:

The Lovász number of a complementary graph is also a lower bound on the chromatic number:

154: 8: 8884:(Technical Communication), vol. 35, Harpenden, England: Commonwealth Bureau of Soils 8027: 6697: 6652: 6594: 6457: 6441: 6255: 6233: 6171:

approximated to within 4/3, and the hardness result shows that no (4/3 −

5986: 5281: 5040: 4484: 4236: 3355: 3271: 2880: 1500: 1026:

which counts the number of unlabeled colorings of a graph from a given finite color set.

497:

All non-isomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph

359: 355: 322: 8168: 7538: 5329:

generalize this property, but it is NP-hard to find a perfect ordering of these graphs.

4338:. Faster algorithms are known for 3- and 4-colorability, which can be decided in time 3113:

There is a strong relationship between edge colorability and the graph's maximum degree

79:

assigns a color to each edge so that no two adjacent edges are of the same color, and a

8891: 8693: 8649: 8618: 8425: 8360: 8323: 8180: 8142: 8074: 8063: 8045: 8016: 7907: 7875: 7776: 7709: 7622: 7550: 7509: 7452: 7434: 7401: 7373: 6717: 6702: 6501: 6465: 6425: 6409: 6259: 5982: 5970: 5914: 5836: 5816: 5790: 5774: 5767: 5753: 5587: 5517: 5318: 4146: 4115: 3378: 2917: 2488: 2432: 2321: 2233: 2145: 1974: 1883: 1729: 1721: 1360: 1340: 1019: 933: 273: 222: 218: 187: 163: 8735: 8489:

Marx, Dániel (2004), "Graph colouring problems and their applications in scheduling",

8210: 7736: 7588: 6414:

An improper vertex coloring where every color class induces a bounded degree subgraph.

5985:, and it is possible to find such a coloring in polynomial time. However, finding the 69:

of a graph such that no two adjacent vertices are of the same color; this is called a

8898: 8835: 8777: 8751: 8721: 8610: 8560: 8511: 8476: 8415: 8387: 8352: 8313: 8284: 8266: 8246: 8230: 8226: 8196: 8184: 8116: 8020: 8006: 7967: 7940: 7911: 7879: 7827: 7811: 7803: 7699: 7642: 7554: 7520: 7391: 6533: 6401: 6385: 6258:, where the most frequently used values of the compiled program are kept in the fast 6247: 5973:

implies that the 3-coloring problem can be solved in linear time. Further, for every

5789:

showed that this is not possible: any deterministic distributed algorithm requires Ω(

5672: 5278:

vertices can be 2-colored, but has an ordering that leads to a greedy coloring with

5270:

colors. On the other hand, greedy colorings can be arbitrarily bad; for example, the

4873: 8622: 8429: 8146: 8067: 7780: 7713: 7513: 7405: 2837: 333: 8950: 8926: 8817: 8769: 8743: 8713: 8697: 8685: 8659: 8602: 8552: 8526: 8460: 8407: 8348: 8327: 8305: 8222: 8172: 8134: 8112: 8092: 8055: 7998: 7988: 7984: 7980: 7957: 7953: 7930: 7897: 7865: 7842: 7798: 7766: 7731: 7691: 7673: 7632: 7584: 7542: 7499: 7474: 7456: 7444: 7383: 7322: 6640: 6509: 6369: 6243: 6094: 5070: 5008: 4862: 4066: 3716:. Although it is known that such a chromatic polynomial has no zeros in the region 1794:

Several lower bounds for the chromatic bounds have been discovered over the years:

1083:

Assigning distinct colors to distinct vertices always yields a proper coloring, so

999: 289: 250: 8931: 8297:

Kuhn, F. (2009), "Weak graph colorings: distributed algorithms and applications",

8265:(Ph.D. thesis), Dept. CS Ser. Pub. A, vol. A-2004-1, University of Helsinki, 7485: 6273:

colors then any set of variables needed at the same time can be stored in at most

5732:

show that there is a distributed algorithm that reduces the number of colors from

5408: 4464:, and removing any edges between them. The remaining edges originally incident to 2566: 2077:{\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}} 1510:

shows that every graph can be colored with one more color than the maximum vertex

897:-edge-coloring and is equivalent to the problem of partitioning the edge set into 221:

pointed out that Kempe's argument was wrong. However, in that paper he proved the

65:

subject to certain constraints. In its simplest form, it is a way of coloring the

9055: 9043: 9013: 8989: 8976: 8858: 8598: 8570: 8381: 7757: 7684:

Chaitin, G. J. (1982), "Register allocation & spilling via graph colouring",

7448: 6599: 6523: 6221: 6164: 6160: 5937: 5827: 5683: 5648: 5644: 5443: 5024: 4876:, so in the worst case the algorithm runs in time within a polynomial factor of 4123: 4103: 3404: 1507: 1496: 179: 111: 8871:

Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms

8551:, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, 7935: 5454:

one after another, expending a previously unused colour when needed. Once a new

4974:

edges. The analysis can be improved to within a polynomial factor of the number

670:

is the smallest positive integer that is not a zero of the chromatic polynomial

8664: 8260: 7992: 7592: 7570:"A colour problem for infinite graphs and a problem in the theory of relations" 7413: 6692: 6626: 6549: 6433: 6213: 6133: 5314: 3615: 3389: 1871: 1138: 1134: 949: 818: 731: 281: 235: 61:; it is an assignment of labels traditionally called "colors" to elements of a 58: 42: 8955: 8583: 8556: 8411: 8176: 7846: 7677: 7619:

Proceedings of the 51st Annual ACM SIGACT Symposium on the Theory of Computing

7546: 6577:

An improper vertex coloring where every color class induces a union of cliques

5850:

since the constant factor 1/2 cannot be improved due to Linial's lower bound.

4959:{\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})} 9071: 8918:

48th International Colloquium on Automata, Languages, and Programming (ICALP)

8822: 8614: 8507: 8334: 8234: 8059: 6658: 6588: 6557: 6541: 6493: 6479: 6313: 6303: 5924:) time in this model. The lower bound for distributed vertex coloring due to 5905:

The problem of edge coloring has also been studied in the distributed model.

5420: 5310: 4119: 2868: 1867: 1503:

and forests. By the four color theorem, every planar graph can be 4-colored.

876: 662:

The chromatic polynomial includes more information about the colorability of

231: 211: 199: 171: 159: 75: 31: 8799:

Tutte, W.T. (1954), "A contribution on the theory of chromatic polynomial",

8773: 8747: 8706:

Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995)

8309: 7853: 7637: 7565: 7387: 3142:. Since all edges incident to the same vertex need their own color, we have 2998: 37: 8531: 7902: 7870: 6910: 6876: 6874: 6676: 6580: 5966: 3359: 2875:): There exist triangle-free graphs with arbitrarily high chromatic number. 265: 207: 175: 106:

The convention of using colors originates from coloring the countries of a

84: 50: 8002: 7771: 7695: 7504: 6470:

Each adjacent incidence of vertex and edge is colored with distinct colors

2980: 1313: 8436: 8031: 7918: 6572: 6422:

An improper vertex coloring that destroys all the symmetries of the graph

5950: 5729: 5725: 5656: 5652: 5271: 5012: 4288: 4107: 3881: 3623: 2852: 2841: 1213:

colors. In an optimal coloring there must be at least one of the graph's

1067: 929: 792: 254: 6871: 6566:, then every path between them contain a vertex with color greater than 4480:). This operation plays a major role in the analysis of graph coloring. 4118:. More generally, the chromatic number and a corresponding coloring of 95:, and a face coloring of a plane graph is just a vertex coloring of its 9048: 8717: 8606: 6849: 6847: 6680: 6634: 6615: 6393: 6377: 5763:) communication steps (assuming that we have unique node identifiers). 3015: 904:. The smallest number of colors needed for an edge coloring of a graph 768: 614: 116: 96: 92: 9061: 9011:

Suite of 8 different algorithms (implemented in C++) used in the book

8689: 7963:

Computers and Intractability: A Guide to the Theory of NP-Completeness

7478: 6390:

Motivated by task systems in which production proceeds in a cyclic way

5431:

Two well-known polynomial-time heuristics for graph colouring are the

8790:

Tutte, W.T. (1949), "On the imbedding of linear graphs in surfaces",

4640:

The chromatic polynomial satisfies the following recurrence relation

3001:): There exist graphs of arbitrarily high girth and chromatic number. 1647: 9049:

Code for efficiently computing Tutte, Chromatic and Flow Polynomials

8464: 8337:(1976), "A note on the complexity of the chromatic number problem", 8138: 8096: 7994:

Proceedings of the Sixth Annual ACM Symposium on Theory of Computing

6844: 5029: 4837:

have different colors, then we might as well consider a graph where

170:

The first results about graph coloring deal almost exclusively with

8050: 7627: 7439: 7040: 7038: 6518:

and difference of colors of vertices at a distance two is at least

6239: 100: 8654: 7828:"Complexity analysis of a decentralised graph colouring algorithm" 7378: 7343:, pp. 172–179, Section 6.4: Latin squares and sudoku puzzles. 7066: 8361:"A self-managed distributed channel selection algorithm for WLAN" 7192: 7190: 6751: 6604:

Every color appears in every partition of equal size exactly once

6180: 6013: 3985: 3950: 3638:-chromatic graphs the complete graphs are the ones with smallest 378: 8964: 7886:

Fawcett, B. W. (1978), "On infinite full colourings of graphs",

7078: 7035: 4868:

These expressions give rise to a recursive procedure called the

4573:{\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}} 2836:

have a high chromatic number, but the opposite is not true. The

998:

For a graph G with a strong embedding on an orientable surface,

515:(blue) admits a 3-coloring; the other graphs admit a 2-coloring. 225:, saying that every planar map can be colored with no more than 8156:

Mathematical Proceedings of the Cambridge Philosophical Society

7319:, pp. 247–276, Chapter 9: Designing university timetables. 7214: 6946: 6286: 5605: 5432: 3806: 124: 8211:"Planar graph coloring is not self-reducible, assuming P ≠ NP" 7187: 6922: 6490:

A color of edges meeting in a common vertex must be contiguous

6151:

for evaluating the chromatic polynomial at any rational point

6079:{\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1} 4853:

have the same colors, we might as well consider a graph where

1439:

colors, for the family of the perfect graphs this function is

455:. A subset of vertices assigned to the same color is called a 7825: 7117: 6148: 6008: > 0, approximating the chromatic number within 5854:

use network decompositions to compute a Δ+1 coloring in time

5400:{\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}} 4076: 9028: 9006: 3377:

For planar graphs, vertex colorings are essentially dual to

467:-coloring is the same as a partition of the vertex set into 249:

to study the coloring problem, which was generalised to the

8123:

Holyer, I. (1981), "The NP-completeness of edge-coloring",

7151: 3891: 127:. Graph coloring is still a very active field of research. 9033:

by Jim Andrews and Mike Fellows is a graph coloring puzzle

8034:(July 2008), "Inapproximability of the Tutte polynomial", 7226: 6982: 6934: 6478:

A set of vertex colorings induced by perfect matchings of

6093:

Computing the coefficients of the chromatic polynomial is

5928:

applies to the distributed edge coloring problem as well.

178:. While trying to color a map of the counties of England, 8742:, Association for Computing Machinery, pp. 257–266, 7462: 7250: 6880: 6209:, the optimal time to finish all jobs without conflicts. 3504:{\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.} 369:

for vertex labels goes back to map coloring. Labels like

107: 8637: 8584:"Some simple distributed algorithms for sparse networks" 8539: 8301:

Symposium on Parallelism in Algorithms and Architectures

8262:

Sum-Product Algorithms for the Analysis of Genetic Risks

7488:(1979), "New methods to color the vertices of a graph", 7295:, pp. 221–246, Chapter 8: Designing sports leagues. 7202: 6853: 6216:, so the coloring problem can be solved efficiently. In 3371: 397:. The smallest number of colors needed to color a graph 268:

formulated another conjecture about graph coloring, the

214:

and later President of the London Mathematical Society.

9014:

A Guide to Graph Colouring: Algorithms and Applications

8768:, Association for Computing Machinery, pp. 35–44, 8383:

A Guide to Graph Colouring: Algorithms and Applications

7923:

Proc. 13th Annual International Conference, COCOON 2007

7744:

Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. (1990),

7307:, pp. 203–220, Chapter 7: Designing seating plans. 7163: 6994: 6832: 6651:

The edges are colored so that each color class forms a

6593:

Every 2-chromatic subgraph is a disjoint collection of

2135:{\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)} 1789: 1078: 936:

is equivalent to the assertion that every planar cubic

8073: 7979: 7129: 7072: 6898: 6763: 6514:

Difference of colors at adjacent vertices is at least

6030: 5996:

computes a coloring of size at most within a factor O(

5989:

smallest 4-coloring of a planar graph is NP-complete.

5671:, graph coloring is closely related to the problem of 5662: 4889: 3606:

concerning the chromatic number of graphs include the

2368: 2168: 2027: 986:

For a graph with a strong embedding on a surface, the

7743: 7687:

Proc. 1982 SIGPLAN Symposium on Compiler Construction

7175: 7060: 6326: 6220:

to radio stations, the resulting conflict graph is a

6103: 6029: 5860: 5614: 5590: 5540: 5520: 5484: 5342: 5284: 5247: 5214: 5187: 5160: 5133: 5106: 5079: 5043: 4980: 4882: 4790: 4757: 4649: 4601: 4496: 4427: 4380: 4344: 4301: 4253: 4232:, impractical for all but the smallest input graphs. 4194: 4159: 3754: 3722: 3690: 3655: 3517: 3452: 3321: 3301: 3281: 3215: 3151: 3119: 3055: 3023: 2956: 2927: 2893: 2708: 2648: 2580: 2514: 2491: 2455: 2435: 2403: 2344: 2324: 2259: 2236: 2148: 2090: 1997: 1977: 1945: 1906: 1886: 1870:

this bound is tight. Finding cliques is known as the

1822: 1739: 1691: 1656: 1611: 1576: 1523: 1445: 1407: 1383: 1363: 1343: 1320: 1294: 1226: 1177: 1146: 1092: 1041: 974:

is the fewest colors needed in any total coloring of

131:

Note: Many terms used in this article are defined in

8763: 8733: 8439:(1992), "Locality in distributed graph algorithms", 7084: 7044: 7025: 7023: 7021: 6820: 6585:

The criterion of minimalization is the sum of colors

6538:

Takes into account orientation of edges of the graph

6320:, which states that in any coloring of the edges of 5969:. On graphs with maximal degree 3 or less, however, 2827: 2623:{\displaystyle \vartheta ({\bar {G}})\leq \chi (G).} 433:

of a graph. A graph that can be assigned a (proper)

321:. One of the major applications of graph coloring, 27:

Methodic assignment of colors to elements of a graph

8628: 8152: 7917: 7274: 7220: 6952: 5851: 162:using colors to show political divisions using the 8967:[On some properties of linear complexes], 8890: 7826:Duffy, K.; O'Connell, N.; Sapozhnikov, A. (2008), 7616: 7526:Proceedings of the Cambridge Philosophical Society 7238: 7196: 7139: 7006: 6886: 6339: 6124: 6078: 5895:{\displaystyle 2^{O\left({\sqrt {\log n}}\right)}} 5894: 5632: 5596: 5576: 5526: 5506: 5399: 5313:, and for special cases of chordal graphs such as 5298: 5262: 5233: 5200: 5173: 5146: 5119: 5092: 5057: 4995: 4958: 4820: 4772: 4732: 4616: 4572: 4456:is the graph obtained by identifying the vertices 4444: 4402: 4366: 4326: 4275: 4224: 4172: 3781: 3740: 3708: 3676: 3588: 3503: 3333: 3307: 3287: 3250: 3189: 3134: 3102: 3038: 2971: 2942: 2908: 2816: 2688: 2622: 2554: 2497: 2477: 2441: 2421: 2389: 2330: 2299: 2242: 2222: 2154: 2134: 2076: 1983: 1963: 1931: 1892: 1855: 1769: 1712: 1677: 1638: 1597: 1559: 1484: 1431: 1393: 1369: 1349: 1326: 1304: 1277: 1205: 1159: 1122: 1056: 9058:by Gary Haggard, David J. Pearce and Gordon Royle 8209:Khuller, Samir; Vazirani, Vijay V. (1991-09-30), 7018: 6958: 6859: 6808: 6406:Every pair of colors appears on at least one edge 5698:}. Put otherwise, we assume that we are given an 337:This graph can be 3-colored in 12 different ways. 9069: 8923:Leibniz International Proceedings in Informatics 8881:The design and analysis of factorial experiments 8672:Scott, Alex; Seymour, Paul (2020), "A survey of 7991:(1974), "Some simplified NP-complete problems", 7331:, pp. 5–6, Section 1.1.3: Scheduling taxis. 7262: 6970: 6462:Every pair of colors appears on at most one edge 6438:Every pair of colors appears on exactly one edge 6430:The sizes of color classes differ by at most one 6004:)(log n)) of the chromatic number. For all 3005: 2192: 2118: 2096: 2056: 2035: 530:four colors, there are 4! = 24 valid colorings ( 8208: 7523:(1941), "On colouring the nodes of a network", 7157: 5909:achieve a (2Δ − 1)-coloring in 5332:If the vertices are ordered according to their 4247:-colorability can be decided in time and space 3610:stating that every graph with chromatic number 2223:{\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)} 8712:, vol. 1004, Springer, pp. 224–233, 8703: 8581: 8491:Periodica Polytechnica, Electrical Engineering 8470: 8026: 7657:On coloring problems of families of prototypes 7560: 7411: 7357:Barenboim, L.; Elkin, M. (2009), "Distributed 7356: 7232: 7096: 6988: 6940: 6757: 5949:Graph coloring is computationally hard. It is 5906: 3412: 2390:{\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}} 1217:edges between every pair of color classes, so 506:(red) admits a 1-coloring; the complete graph 9025:by Joseph Culberson (graph coloring programs) 8358: 8079:"Parallel symmetry-breaking in sparse graphs" 7754: 7659:(PhD thesis), Boulder: University of Colorado 7256: 7113: 6362:Adjacent-vertex-distinguishing-total coloring 6224:, so the coloring problem is 3-approximable. 6063: 6034: 5336:, the resulting greedy coloring uses at most 5037:vertices, where the greedy algorithm expends 2883:but with arbitrarily large chromatic number. 2338:be a positive semi-definite matrix such that 328: 8856: 8671: 8582:Panconesi, Alessandro; Rizzi, Romeo (2001), 8549:Sparsity: Graphs, Structures, and Algorithms 8475:(2nd ed.), Cambridge University Press, 7952: 7929:, vol. 4598, Springer, pp. 65–74, 7208: 7133: 6838: 6057: 6043: 5394: 5360: 4567: 4517: 2142:are the largest and smallest eigenvalues of 1278:{\displaystyle \chi (G)(\chi (G)-1)\leq 2m.} 1070:of the coefficients in the coloring vector. 990:is the dual of the vertex coloring problem. 257:, both of which are important invariants in 9008:High-Performance Graph Colouring Algorithms 8965:"О некоторых свойствах линейных комплексов" 8807: 8102: 7719: 7169: 7056: 7000: 5944: 5936:Decentralized algorithms are ones where no 5931: 5073:considers the vertices in a specific order 358:have the same color. Since a vertex with a 45:with 3 colors, the minimum number possible. 9017:(Springer International Publishers, 2015). 8190: 6769: 5981:-coloring of a planar graph exists by the 4733:{\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)} 4472:are now incident to their identification ( 4291:'s algorithm for the fast zeta transform, 2689:{\displaystyle \chi _{f}(G)\leq \chi (G).} 2555:{\displaystyle \chi _{V}(G)\leq \chi (G).} 2485:to be the least k for which such a matrix 2300:{\displaystyle \chi _{H}(G)\leq \chi (G).} 1560:{\displaystyle \chi (G)\leq \Delta (G)+1.} 1133:The only graphs that can be 1-colored are 8954: 8938: 8930: 8821: 8663: 8653: 8530: 8506: 8498: 8454: 8077:; Plotkin, S. A.; Shannon, G. E. (1988), 8049: 7934: 7901: 7869: 7810: 7802: 7770: 7735: 7636: 7626: 7503: 7438: 7377: 7181: 7118:Duffy, O'Connell & Sapozhnikov (2008) 6881:Björklund, Husfeldt & Koivisto (2009) 6826: 6498:Each vertex chooses from a list of colors 5154:the smallest available color not used by 3190:{\displaystyle \chi '(G)\geq \Delta (G).} 2959: 2930: 2896: 2872: 1044: 1029:If we interpret a coloring of a graph on 697:Chromatic polynomials for certain graphs 9103:Extensions and generalizations of graphs 8893:Integer Flows and Cycle Covers of Graphs 8258: 7856:(1959), "Graph theory and probability", 7814:(April 1947), "A three colour problem", 6928: 5781:distributed algorithm for 3-coloring an 5694:, for example, from the set {1, 2, ..., 5028: 1856:{\displaystyle \chi (G)\geq \omega (G).} 1485:{\displaystyle c(\omega (G))=\omega (G)} 885:of a graph is a proper coloring of the 666:than does the chromatic number. Indeed, 492: 332: 153: 36: 8471:van Lint, J. H.; Wilson, R. M. (2001), 7885: 7683: 7654: 7280: 6506:Each edge chooses from a list of colors 6097:. In fact, even computing the value of 5478:The worst-case complexity of DSatur is 5426: 3434: 3433:, it admits an infinite full coloring ( 2884: 1770:{\displaystyle \chi (G)\leq \Delta (G)} 1495:The 2-colorable graphs are exactly the 586:The chromatic polynomial is a function 488: 346:When used without any qualification, a 202:raised the problem at a meeting of the 14: 9098:Computational problems in graph theory 9070: 8435: 8333: 8278: 8122: 7786: 7663: 7519: 7484: 7244: 7145: 7130:Garey, Johnson & Stockmeyer (1974) 7073:Goldberg, Plotkin & Shannon (1988) 7012: 6892: 6814: 6745: 6227: 6196:Vertex coloring models to a number of 5925: 5786: 3103:{\displaystyle \chi '(G)=\chi (L(G)).} 1018:of a coloring under the action of the 993: 957:is a type of coloring on the vertices 325:in compilers, was introduced in 1981. 123:the form of the popular number puzzle 8962: 8910: 8888: 8877: 8798: 8789: 8399: 8386:, Springer International Publishing, 8379: 8240: 7852: 7340: 7328: 7316: 7304: 7292: 7029: 6964: 6916: 6904: 6865: 6803: 6792: 6781: 6643:has a color that is used exactly once 6374:Every 2-chromatic subgraph is acyclic 6280: 4584: 4295:-colorability can be decided in time 2864: 2856: 2699:These bounds are ordered as follows: 1900:be a real symmetric matrix such that 1123:{\displaystyle 1\leq \chi (G)\leq n.} 1066:, the action of an automorphism is a 1005: 609:. As the name indicates, for a given 350:of a graph almost always refers to a 318: 9037:Links to Graph Coloring source codes 8847: 8829: 8488: 8296: 8084:SIAM Journal on Discrete Mathematics 7577:Nederl. Akad. Wetensch. Proc. Ser. A 7268: 7100: 7061:Cormen, Leiserson & Rivest (1990 6976: 6675:Coloring can also be considered for 6562:If two vertices have the same color 6355: 6350: 5953:to decide if a given graph admits a 5720:The simplest interesting case is an 3857:admit a proper vertex coloring with 3372:Nešetřil & Ossona de Mendez 2012 3251:{\displaystyle \chi '(G)=\Delta (G)} 1790:Lower bounds on the chromatic number 1785:is a complete graph or an odd cycle. 1079:Upper bounds on the chromatic number 309: 7221:Jaeger, Vertigan & Welsh (1990) 6953:Fomin, Gaspers & Saurabh (2007) 5800:) communication steps to reduce an 5663:Parallel and distributed algorithms 4483:The chromatic number satisfies the 4141: 3354:-coloring if and only if it has an 3345: 451:if its chromatic number is exactly 24: 8359:Leith, D.J.; Clifford, P. (2006), 7197:Bulín, Krokhin & Opršal (2019) 7085:Schneider & Wattenhofer (2008) 7045:Schneider & Wattenhofer (2010) 6546:Models a routing problem in graphs 6292: 6038: 5846:)/2, which is optimal in terms of 5018: 4097: 3732: 3700: 3555: 3483: 3322: 3302: 3282: 3236: 3172: 3120: 2887:constructed axis aligned boxes in 1755: 1692: 1612: 1539: 1386: 1297: 341: 194:, who mentioned it in a letter to 25: 9114: 9000: 8710:Lecture Notes in Computer Science 8283:, American Mathematical Society, 7927:Lecture Notes in Computer Science 6175: )-algorithm exists for any 5852:Panconesi & Srinivasan (1996) 5826:). The technique was extended to 5468:recursive largest first algorithm 5007:of the input graph. In practice, 3822:Graph coloring, vertex coloring, 2828:Graphs with high chromatic number 943: 146:History of the four color theorem 8911:Zamir, Or (2021), "Breaking the 8493:, vol. 48, pp. 11–16, 8195:, Wiley-Interscience, New York, 8191:Jensen, T. R.; Toft, B. (1995), 7369:Symposium on Theory of Computing 6318:theorem on friends and strangers 6312:coloring problems is studied in 6297: 5804:-coloring to a 3-coloring in an 5412:algorithms are sometimes called 4153:-coloring considers each of the 3805: 3441: 3368:Gallai–Hasse–Roy–Vitaver theorem 2972:{\displaystyle \mathbb {R} ^{2}} 2943:{\displaystyle \mathbb {R} ^{3}} 2909:{\displaystyle \mathbb {R} ^{3}} 1057:{\displaystyle \mathbb {Z} ^{d}} 981: 870: 471:independent sets, and the terms 41:A proper vertex coloring of the 8857:Wrochna, M.; Živný, S. (2020), 8641:Journal of Combinatorial Theory 7858:Canadian Journal of Mathematics 7655:Burling, James Perkins (1965), 7123: 7106: 7090: 7050: 6186: 5702:-coloring. The challenge is to 4595:are non-adjacent vertices, and 4225:{\displaystyle k=1,\ldots ,n-1} 270:strong perfect graph conjecture 8512:"Sur le coloriage des graphes" 8340:Information Processing Letters 8105:Information Processing Letters 7835:Information Processing Letters 6989:Sekine, Imai & Tani (1995) 6797: 6786: 6775: 6734: 6631:Vertices and edges are colored 6119: 6107: 5679:by Schneider and Wattenhofer. 5627: 5618: 5577:{\displaystyle O((n+m)\log n)} 5571: 5559: 5547: 5544: 5501: 5488: 5379: 5366: 5257: 5251: 4990: 4984: 4953: 4934: 4870:deletion–contraction algorithm 4815: 4794: 4727: 4715: 4706: 4683: 4674: 4653: 4564: 4547: 4538: 4523: 4506: 4500: 4413: 4397: 4384: 4361: 4348: 4321: 4305: 4270: 4257: 3770: 3758: 3735: 3723: 3703: 3691: 3671: 3659: 3564: 3558: 3549: 3543: 3527: 3521: 3492: 3486: 3477: 3471: 3462: 3456: 3403:, under the assumption of the 3388:If all finite subgraphs of an 3245: 3239: 3230: 3224: 3181: 3175: 3166: 3160: 3129: 3123: 3094: 3091: 3085: 3079: 3070: 3064: 3033: 3027: 2808: 2802: 2793: 2787: 2771: 2765: 2756: 2747: 2741: 2725: 2719: 2680: 2674: 2665: 2659: 2614: 2608: 2599: 2593: 2584: 2546: 2540: 2531: 2525: 2472: 2466: 2416: 2404: 2291: 2285: 2276: 2270: 2217: 2211: 2185: 2179: 2129: 2123: 2107: 2101: 2067: 2061: 2046: 2040: 2014: 2008: 1958: 1946: 1847: 1841: 1832: 1826: 1777:for a connected, simple graph 1764: 1758: 1749: 1743: 1701: 1695: 1666: 1660: 1639:{\displaystyle \Delta (G)=n-1} 1621: 1615: 1586: 1580: 1548: 1542: 1533: 1527: 1479: 1473: 1464: 1461: 1455: 1449: 1426: 1423: 1417: 1411: 1394:{\displaystyle {\mathcal {F}}} 1305:{\displaystyle {\mathcal {F}}} 1260: 1251: 1245: 1239: 1236: 1230: 1206:{\displaystyle \chi (K_{n})=n} 1194: 1181: 1108: 1102: 940:graph admits a Tait coloring. 315:Karp's 21 NP-complete problems 13: 1: 8984:. Translated into English in 8932:10.4230/LIPIcs.ICALP.2021.113 8803:, vol. 6, pp. 80–91 8406:, Texts in Computer Science, 8368:Proc. RAWNET 2006, Boston, MA 7750:(1st ed.), The MIT Press 7737:10.1016/S0019-9958(86)80023-7 7589:10.1016/S1385-7258(51)50053-7 7349: 7158:Khuller & Vazirani (1991) 6919:, Chapter 4.6.4, pp. 501-502. 6191: 4403:{\displaystyle O(1.7272^{n})} 4367:{\displaystyle O(1.3289^{n})} 4276:{\displaystyle O(2.4423^{n})} 4239:and a bound on the number of 3792: 3628:Erdős–Faber–Lovász conjecture 3600:chromatic number of the plane 3006:Bounds on the chromatic index 1432:{\displaystyle c(\omega (G))} 1073: 534:assignment of four colors to 272:, originally motivated by an 8986:Amer. Math. Soc. Translation 8832:Introduction to Graph Theory 8738:; Guerraoui, Rachid (eds.), 8353:10.1016/0020-0190(76)90065-X 8259:Koivisto, Mikko (Jan 2004), 8241:Knuth, Donald Ervin (1997), 8227:10.1016/0304-3975(91)90081-C 8215:Theoretical Computer Science 8117:10.1016/0020-0190(93)90246-6 7804:10.1016/0012-365X(80)90236-8 7449:10.1016/j.jalgor.2004.06.008 7416:(2005), "3-coloring in time 7233:Goldberg & Jerrum (2008) 7097:Barenboim & Elkin (2009) 6941:Beigel & Eppstein (2005) 6758:van Lint & Wilson (2001) 6155: ≥ 1.5 except for 6147: = 2. There is no 5907:Panconesi & Rizzi (2001) 5323:perfect elimination ordering 3782:{\displaystyle P(G,4)\neq 0} 3413:de Bruijn & Erdős (1951) 3014:is a vertex coloring of its 2950:as well as line segments in 2478:{\displaystyle \chi _{V}(G)} 1713:{\displaystyle \Delta (G)=2} 1401:can be colored with at most 459:, every such class forms an 390:colors is called a (proper) 286:strong perfect graph theorem 7: 8971:, New Series (in Russian), 8037:Information and Computation 7936:10.1007/978-3-540-73545-8_9 7666:Operations Research Letters 7257:Crescenzi & Kann (1998) 7114:Leith & Clifford (2006) 6686: 6647:Triangle-free edge coloring 4780:is the graph with the edge 4751:are adjacent vertices, and 4624:is the graph with the edge 3741:{\displaystyle [5,\infty )} 3709:{\displaystyle [4,\infty )} 3684:has no zeros in the region 2635:Fractional chromatic number 429:is also used to denote the 204:London Mathematical Society 10: 9119: 8665:10.1016/j.jctb.2013.11.001 7747:Introduction to Algorithms 7209:Wrochna & Živný (2020) 7134:Garey & Johnson (1979) 6839:Scott & Seymour (2020) 6301: 6231: 6125:{\displaystyle \chi (G,k)} 5706:the number of colors from 5444:greedy colouring algorithm 5327:perfectly orderable graphs 5022: 3295:has edge-chromatic number 3275:A graph of maximal degree 3135:{\displaystyle \Delta (G)} 1678:{\displaystyle \chi (G)=3} 1598:{\displaystyle \chi (G)=n} 1337:if there is some function 947: 928:is a 3-edge coloring of a 874: 601:that counts the number of 518: 329:Definition and terminology 143: 139: 29: 9064:by Jose Antonio Martin H. 8956:10.4086/toc.2007.v003a006 8850:Algorithms and Complexity 8557:10.1007/978-3-642-27875-4 8545:Ossona de Mendez, Patrice 8473:A Course in Combinatorics 8442:SIAM Journal on Computing 8412:10.1007/978-3-030-81054-2 8177:10.1017/S0305004100068936 8126:SIAM Journal on Computing 7847:10.1016/j.ipl.2008.01.002 7678:10.1016/j.orl.2004.03.002 7547:10.1017/S030500410002168X 7491:Communications of the ACM 7466:SIAM Journal on Computing 7057:Cole & Vishkin (1986) 7001:Welsh & Powell (1967) 6742:History of graph coloring 6474:Inherited vertex coloring 4821:{\displaystyle P(G-uv,k)} 4327:{\displaystyle O(2^{n}n)} 4283:. Using the principle of 4106:, and thus computable in 4083: 4072: 4062: 4050: 4023: 4004: 3996: 3991: 3976: 3956: 3946: 3934: 3918: 3910: 3905: 3897: 3887: 3877: 3865: 3849: 3830: 3818: 3813: 3804: 3799: 3418:If a graph admits a full 3334:{\displaystyle \Delta +1} 1932:{\displaystyle W_{i,j}=0} 621:. For the example graph, 613:the function is indeed a 386:A coloring using at most 365:The terminology of using 280:of a graph introduced by 9062:A graph coloring Web App 8889:Zhang, Cun-Quan (1997), 8794:, 2,51, pp. 474–483 8547:(2012), "Theorem 3.13", 8403:Guide to Graph Colouring 8400:Lewis, R. M. R. (2021), 8380:Lewis, R. M. R. (2016), 8299:Proceedings of the 21st 8243:Seminumerical Algorithms 8060:10.1016/j.ic.2008.04.003 7367:Proceedings of the 41st 7361:-coloring in linear (in 6770:Jensen & Toft (1995) 6728: 6723:Uniquely colorable graph 5945:Computational complexity 5932:Decentralized algorithms 5507:{\displaystyle O(n^{2})} 5263:{\displaystyle \chi (G)} 4241:maximal independent sets 4128:semidefinite programming 3046:, and vice versa. Thus, 1288:More generally a family 1033:vertices as a vector in 206:in 1879. The same year, 133:Glossary of graph theory 30:Not to be confused with 8859:"Improved hardness for 8792:Proc. London Math. Soc. 8774:10.1145/1400751.1400758 8748:10.1145/1835698.1835760 8678:Journal of Graph Theory 8597:(2), Berlin, New York: 8310:10.1145/1583991.1584032 8193:Graph Coloring Problems 7723:Information and Control 7638:10.1145/3313276.3316300 7388:10.1145/1536414.1536432 6522:. A particular case is 6418:Distinguishing coloring 5994:approximation algorithm 5472:maximal independent set 5437:recursive largest first 5234:{\displaystyle v_{i-1}} 4091:unless P = NP 3409:de Bruijn–Erdős theorem 3399:-colorable, then so is 3308:{\displaystyle \Delta } 3288:{\displaystyle \Delta } 2313:Vector chromatic number 485:have the same meaning. 405:, and is often denoted 150:History of graph theory 8823:10.1093/comjnl/10.1.85 8532:10.4064/cm-3-2-161-162 7903:10.4153/cjm-1978-039-8 7871:10.4153/CJM-1959-003-9 6931:, pp. 45, 96–103. 6486:Interval edge coloring 6341: 6308:An important class of 6159: = 2 unless 6126: 6080: 6023:-colorable graph with 5961:except for the cases 5957:-coloring for a given 5896: 5677:multi-trials technique 5669:distributed algorithms 5634: 5598: 5578: 5528: 5508: 5401: 5300: 5264: 5235: 5202: 5175: 5148: 5121: 5094: 5066: 5059: 4997: 4960: 4822: 4774: 4734: 4618: 4574: 4446: 4404: 4368: 4328: 4277: 4226: 4174: 3783: 3742: 3710: 3678: 3677:{\displaystyle P(G,t)} 3590: 3505: 3335: 3309: 3289: 3252: 3191: 3136: 3104: 3040: 2973: 2944: 2910: 2818: 2690: 2624: 2556: 2499: 2479: 2443: 2423: 2391: 2332: 2301: 2244: 2224: 2156: 2136: 2078: 1985: 1965: 1933: 1894: 1857: 1771: 1714: 1679: 1640: 1599: 1561: 1486: 1433: 1395: 1371: 1351: 1328: 1306: 1279: 1207: 1161: 1124: 1058: 516: 352:proper vertex coloring 338: 259:algebraic graph theory 167: 46: 18:Cole-Vishkin algorithm 8963:Zykov, A. A. (1949), 8631:Journal of Algorithms 8591:Distributed Computing 8003:10.1145/800119.803884 7772:10.1145/306198.306210 7696:10.1145/800230.806984 7505:10.1145/359094.359101 7426:Journal of Algorithms 6713:Mathematics of Sudoku 6342: 6340:{\displaystyle K_{6}} 6252:compiler optimization 6127: 6081: 5897: 5635: 5633:{\displaystyle O(mn)} 5599: 5579: 5529: 5509: 5446:, DSatur colours the 5402: 5301: 5265: 5236: 5203: 5201:{\displaystyle v_{1}} 5176: 5174:{\displaystyle v_{i}} 5149: 5147:{\displaystyle v_{i}} 5122: 5120:{\displaystyle v_{n}} 5095: 5093:{\displaystyle v_{1}} 5060: 5032: 4998: 4961: 4823: 4775: 4735: 4619: 4575: 4476:, the new fused node 4447: 4405: 4369: 4329: 4278: 4227: 4175: 4173:{\displaystyle k^{n}} 3784: 3743: 3711: 3679: 3591: 3506: 3336: 3310: 3290: 3253: 3192: 3137: 3105: 3041: 2974: 2945: 2911: 2819: 2691: 2625: 2557: 2500: 2480: 2444: 2424: 2422:{\displaystyle (i,j)} 2392: 2333: 2302: 2245: 2225: 2157: 2137: 2079: 1986: 1966: 1964:{\displaystyle (i,j)} 1934: 1895: 1858: 1772: 1715: 1680: 1641: 1600: 1570:Complete graphs have 1562: 1487: 1434: 1396: 1372: 1357:such that the graphs 1352: 1329: 1327:{\displaystyle \chi } 1307: 1280: 1208: 1162: 1160:{\displaystyle K_{n}} 1125: 1059: 914:edge chromatic number 496: 336: 274:information-theoretic 243:George David Birkhoff 184:four color conjecture 157: 57:is a special case of 40: 9088:NP-complete problems 8873:, pp. 1426–1435 8848:Wilf, H. S. (1986), 8830:West, D. B. (1996), 8810:The Computer Journal 8304:, pp. 138–144, 7790:Discrete Mathematics 7621:, pp. 602–613, 7372:, pp. 111–120, 6854:Pawlik et al. (2014) 6608:Strong edge coloring 6450:Hamiltonian coloring 6324: 6246:that translates one 6218:bandwidth allocation 6143: = 1 and 6101: 6027: 5858: 5612: 5588: 5538: 5518: 5482: 5461:degree of saturation 5427:Heuristic algorithms 5340: 5282: 5245: 5212: 5185: 5181:'s neighbours among 5158: 5131: 5104: 5077: 5041: 4996:{\displaystyle t(G)} 4978: 4880: 4788: 4773:{\displaystyle G-uv} 4755: 4647: 4617:{\displaystyle G+uv} 4599: 4494: 4445:{\displaystyle G/uv} 4425: 4378: 4342: 4299: 4251: 4192: 4157: 4112:breadth-first search 4079:for restricted cases 4000:Chromatic polynomial 3752: 3720: 3688: 3653: 3632:Albertson conjecture 3515: 3450: 3422:-coloring for every 3319: 3299: 3279: 3213: 3149: 3117: 3053: 3039:{\displaystyle L(G)} 3021: 3010:An edge coloring of 2954: 2925: 2891: 2881:triangle-free graphs 2853:William T. Tutte 2706: 2646: 2578: 2512: 2489: 2453: 2433: 2401: 2342: 2322: 2257: 2234: 2166: 2146: 2088: 1995: 1975: 1943: 1904: 1884: 1820: 1737: 1689: 1654: 1609: 1574: 1521: 1443: 1405: 1381: 1361: 1341: 1318: 1292: 1224: 1175: 1144: 1090: 1039: 1024:chromatic polynomial 565:Number of colorings 527:chromatic polynomial 521:Chromatic polynomial 489:Chromatic polynomial 431:Euler characteristic 247:chromatic polynomial 9022:Graph Coloring Page 8942:Theory of Computing 8867:-colourable graphs" 8279:Kubale, M. (2004), 8169:1990MPCPS.108...35J 7690:, pp. 98–105, 7539:1941PCPS...37..194B 6698:Graph coloring game 6480:edge-colored Graphs 6458:Harmonious coloring 6442:Fractional coloring 6260:processor registers 6256:register allocation 6234:Register allocation 6228:Register allocation 6198:scheduling problems 6000:(log log 5728:. Richard Cole and 5643:DSatur and RLF are 5463:of a given vertex. 5414:sequential coloring 5325:for the graph. The 5319:indifference graphs 5299:{\displaystyle n/2} 5058:{\displaystyle n/2} 4485:recurrence relation 4285:inclusion–exclusion 4237:dynamic programming 4122:can be computed in 3608:Hadwiger conjecture 3362:has length at most 3356:acyclic orientation 2861:Alexander Zykov 994:Tutte’s flow theory 893:colors is called a 698: 323:register allocation 278:zero-error capacity 276:concept called the 9054:2008-04-16 at the 9042:2008-07-04 at the 8878:Yates, F. (1937), 8718:10.1007/BFb0015427 8607:10.1007/PL00008932 8541:Nešetřil, Jaroslav 7997:, pp. 47–63, 7812:Descartes, Blanche 7170:Halldórsson (1993) 6718:Multipartite graph 6708:Hajós construction 6703:Graph homomorphism 6502:List edge-coloring 6466:Incidence coloring 6426:Equitable coloring 6410:Defective coloring 6337: 6281:Other applications 6267:interference graph 6177:ε > 0 6132:is #P-hard at any 6122: 6076: 6075: 5983:four color theorem 5892: 5775:iterated logarithm 5630: 5594: 5574: 5524: 5504: 5439:(RLF) algorithms. 5397: 5296: 5260: 5231: 5198: 5171: 5144: 5117: 5090: 5067: 5055: 4993: 4956: 4910: 4818: 4770: 4730: 4614: 4570: 4442: 4400: 4364: 4324: 4273: 4222: 4170: 4147:Brute-force search 4116:depth-first search 4016:vertices. Integer 3842:vertices. Integer 3779: 3738: 3706: 3674: 3586: 3501: 3379:nowhere-zero flows 3331: 3305: 3285: 3248: 3187: 3132: 3100: 3036: 2969: 2940: 2918:intersection graph 2906: 2832:Graphs with large 2814: 2686: 2620: 2552: 2495: 2475: 2439: 2419: 2387: 2385: 2328: 2297: 2240: 2220: 2200: 2152: 2132: 2074: 2072: 1981: 1971:is not an edge in 1961: 1929: 1890: 1853: 1767: 1710: 1675: 1636: 1595: 1557: 1482: 1429: 1391: 1367: 1347: 1324: 1302: 1275: 1203: 1171:vertices requires 1157: 1120: 1054: 1020:automorphism group 1012:unlabeled coloring 1006:Unlabeled coloring 934:four color theorem 696: 517: 339: 223:five color theorem 219:Percy John Heawood 192:University College 188:Augustus De Morgan 168: 164:four color theorem 47: 8904:978-0-8247-9790-4 8834:, Prentice-Hall, 8783:978-1-59593-989-0 8757:978-1-60558-888-9 8690:10.1002/jgt.22601 8566:978-3-642-27874-7 8421:978-3-030-81053-5 8393:978-3-319-25728-0 8319:978-1-60558-606-9 7946:978-3-540-73544-1 7648:978-1-4503-6705-9 7479:10.1137/070683933 7397:978-1-60558-506-2 6672: 6671: 6635:Centered coloring 6534:Oriented coloring 6402:Complete coloring 6386:Circular coloring 6248:computer language 6061: 5987:lexicographically 5884: 5692:unique identifier 5673:symmetry breaking 5597:{\displaystyle m} 5527:{\displaystyle n} 5442:Similarly to the 5358: 5347: 5013:graph isomorphism 4909: 4903: 4874:Fibonacci numbers 4845:are adjacent. If 4515: 4095: 4094: 4084:Inapproximability 3977:Inapproximability 3649:, the polynomial 3577: 3446:As stated above, 3272:Vizing's Theorem: 2869:Jan Mycielski 2768: 2596: 2498:{\displaystyle W} 2442:{\displaystyle G} 2384: 2331:{\displaystyle W} 2243:{\displaystyle W} 2191: 2155:{\displaystyle W} 2071: 1984:{\displaystyle G} 1893:{\displaystyle W} 1370:{\displaystyle G} 1350:{\displaystyle c} 1014:of a graph is an 868: 867: 584: 583: 545:Available colors 313:below) is one of 16:(Redirected from 9110: 9093:NP-hard problems 8983: 8959: 8958: 8935: 8934: 8914: 8907: 8896: 8885: 8874: 8866: 8862: 8853: 8844: 8826: 8825: 8804: 8795: 8786: 8760: 8736:Richa, Andréa W. 8730: 8700: 8675: 8668: 8667: 8657: 8634: 8625: 8588: 8577: 8535: 8534: 8516: 8503: 8502: 8485: 8467: 8458: 8432: 8396: 8376: 8375: 8374: 8365: 8355: 8330: 8293: 8275: 8255: 8237: 8205: 8187: 8149: 8119: 8099: 8070: 8053: 8023: 7976: 7966:, W.H. Freeman, 7949: 7938: 7914: 7905: 7882: 7873: 7849: 7832: 7822: 7807: 7806: 7783: 7774: 7751: 7740: 7739: 7716: 7680: 7660: 7651: 7640: 7630: 7605: 7604: 7603: 7597: 7591:, archived from 7574: 7562:de Bruijn, N. G. 7557: 7516: 7507: 7481: 7459: 7442: 7422: 7408: 7381: 7364: 7360: 7344: 7338: 7332: 7326: 7320: 7314: 7308: 7302: 7296: 7290: 7284: 7278: 7272: 7266: 7260: 7254: 7248: 7242: 7236: 7230: 7224: 7218: 7212: 7206: 7200: 7194: 7185: 7182:Zuckerman (2007) 7179: 7173: 7167: 7161: 7155: 7149: 7143: 7137: 7127: 7121: 7110: 7104: 7094: 7088: 7082: 7076: 7070: 7064: 7063:, Section 30.5). 7054: 7048: 7042: 7033: 7027: 7016: 7010: 7004: 6998: 6992: 6986: 6980: 6974: 6968: 6962: 6956: 6950: 6944: 6938: 6932: 6926: 6920: 6914: 6908: 6907:, p. 66-67. 6902: 6896: 6890: 6884: 6878: 6869: 6863: 6857: 6851: 6842: 6836: 6830: 6827:Descartes (1947) 6824: 6818: 6812: 6806: 6801: 6795: 6790: 6784: 6779: 6773: 6767: 6761: 6755: 6749: 6738: 6641:induced subgraph 6639:Every connected 6510:L(h, k)-coloring 6370:Acyclic coloring 6356: 6346: 6344: 6343: 6338: 6336: 6335: 6244:computer program 6181:P = NP 6131: 6129: 6128: 6123: 6085: 6083: 6082: 6077: 6068: 6067: 6066: 6060: 6053: 6037: 5918: 5901: 5899: 5898: 5893: 5891: 5890: 5889: 5885: 5874: 5840: 5835:(Δ) + 5828:unit disk graphs 5820: 5794: 5771: 5757: 5667:In the field of 5639: 5637: 5636: 5631: 5603: 5601: 5600: 5595: 5583: 5581: 5580: 5575: 5533: 5531: 5530: 5525: 5513: 5511: 5510: 5505: 5500: 5499: 5406: 5404: 5403: 5398: 5378: 5377: 5359: 5356: 5354: 5353: 5348: 5345: 5305: 5303: 5302: 5297: 5292: 5269: 5267: 5266: 5261: 5240: 5238: 5237: 5232: 5230: 5229: 5207: 5205: 5204: 5199: 5197: 5196: 5180: 5178: 5177: 5172: 5170: 5169: 5153: 5151: 5150: 5145: 5143: 5142: 5127:and assigns to 5126: 5124: 5123: 5118: 5116: 5115: 5099: 5097: 5096: 5091: 5089: 5088: 5071:greedy algorithm 5064: 5062: 5061: 5056: 5051: 5009:branch and bound 5002: 5000: 4999: 4994: 4965: 4963: 4962: 4957: 4952: 4951: 4927: 4926: 4915: 4911: 4905: 4904: 4899: 4890: 4863:Tutte polynomial 4827: 4825: 4824: 4819: 4783: 4779: 4777: 4776: 4771: 4739: 4737: 4736: 4731: 4693: 4627: 4623: 4621: 4620: 4615: 4579: 4577: 4576: 4571: 4557: 4516: 4513: 4451: 4449: 4448: 4443: 4435: 4409: 4407: 4406: 4401: 4396: 4395: 4373: 4371: 4370: 4365: 4360: 4359: 4333: 4331: 4330: 4325: 4317: 4316: 4282: 4280: 4279: 4274: 4269: 4268: 4231: 4229: 4228: 4223: 4179: 4177: 4176: 4171: 4169: 4168: 4142:Exact algorithms 3992:Counting problem 3986:P = NP 3914:Chromatic number 3892:3-Satisfiability 3809: 3797: 3796: 3788: 3786: 3785: 3780: 3747: 3745: 3744: 3739: 3715: 3713: 3712: 3707: 3683: 3681: 3680: 3675: 3595: 3593: 3592: 3587: 3582: 3578: 3573: 3538: 3510: 3508: 3507: 3502: 3346:Other properties 3340: 3338: 3337: 3332: 3314: 3312: 3311: 3306: 3294: 3292: 3291: 3286: 3257: 3255: 3254: 3249: 3223: 3196: 3194: 3193: 3188: 3159: 3141: 3139: 3138: 3133: 3109: 3107: 3106: 3101: 3063: 3045: 3043: 3042: 3037: 2978: 2976: 2975: 2970: 2968: 2967: 2962: 2949: 2947: 2946: 2941: 2939: 2938: 2933: 2915: 2913: 2912: 2907: 2905: 2904: 2899: 2823: 2821: 2820: 2815: 2786: 2785: 2770: 2769: 2761: 2740: 2739: 2718: 2717: 2695: 2693: 2692: 2687: 2658: 2657: 2629: 2627: 2626: 2621: 2598: 2597: 2589: 2561: 2559: 2558: 2553: 2524: 2523: 2504: 2502: 2501: 2496: 2484: 2482: 2481: 2476: 2465: 2464: 2448: 2446: 2445: 2440: 2428: 2426: 2425: 2420: 2396: 2394: 2393: 2388: 2386: 2383: 2369: 2360: 2359: 2337: 2335: 2334: 2329: 2315: 2314: 2306: 2304: 2303: 2298: 2269: 2268: 2250:as above. Then: 2249: 2247: 2246: 2241: 2229: 2227: 2226: 2221: 2210: 2209: 2199: 2178: 2177: 2161: 2159: 2158: 2153: 2141: 2139: 2138: 2133: 2122: 2121: 2100: 2099: 2083: 2081: 2080: 2075: 2073: 2070: 2060: 2059: 2049: 2039: 2038: 2028: 2007: 2006: 1990: 1988: 1987: 1982: 1970: 1968: 1967: 1962: 1938: 1936: 1935: 1930: 1922: 1921: 1899: 1897: 1896: 1891: 1878:Hoffman's bound: 1862: 1860: 1859: 1854: 1809:, then at least 1776: 1774: 1773: 1768: 1719: 1717: 1716: 1711: 1684: 1682: 1681: 1676: 1645: 1643: 1642: 1637: 1604: 1602: 1601: 1596: 1566: 1564: 1563: 1558: 1497:bipartite graphs 1491: 1489: 1488: 1483: 1438: 1436: 1435: 1430: 1400: 1398: 1397: 1392: 1390: 1389: 1376: 1374: 1373: 1368: 1356: 1354: 1353: 1348: 1333: 1331: 1330: 1325: 1311: 1309: 1308: 1303: 1301: 1300: 1284: 1282: 1281: 1276: 1212: 1210: 1209: 1204: 1193: 1192: 1166: 1164: 1163: 1158: 1156: 1155: 1129: 1127: 1126: 1121: 1065: 1063: 1061: 1060: 1055: 1053: 1052: 1047: 1032: 1000:William T. Tutte 977: 973: 969: 923: 907: 900: 896: 892: 864: 813: 800: 787: 774: 763: 739: 726: 710: 699: 695: 693: 669: 665: 658: 647: 620: 612: 608: 604: 600: 542: 541: 514: 505: 482: 475: 470: 466: 454: 448: 441: 436: 428: 420: 412: 403:chromatic number 400: 394: 389: 383: 310:#Vertex coloring 251:Tutte polynomial 196:William Hamilton 73:. Similarly, an 21: 9118: 9117: 9113: 9112: 9111: 9109: 9108: 9107: 9068: 9067: 9056:Wayback Machine 9044:Wayback Machine 9003: 8998: 8975:(66): 163–188, 8912: 8905: 8864: 8863:-colourings of 8860: 8852:, Prentice–Hall 8842: 8801:Canad. J. Math. 8784: 8758: 8728: 8676:-boundedness", 8673: 8599:Springer-Verlag 8586: 8567: 8514: 8483: 8465:10.1137/0221015 8456:10.1.1.471.6378 8422: 8394: 8372: 8370: 8363: 8320: 8291: 8281:Graph Colorings 8273: 8253: 8203: 8139:10.1137/0210055 8097:10.1137/0401044 8075:Goldberg, A. V. 8028:Goldberg, L. A. 8013: 7974: 7947: 7830: 7758:ACM SIGACT News 7706: 7649: 7601: 7599: 7595: 7572: 7433:(2)): 168–204, 7417: 7398: 7362: 7358: 7352: 7347: 7339: 7335: 7327: 7323: 7315: 7311: 7303: 7299: 7291: 7287: 7279: 7275: 7267: 7263: 7255: 7251: 7243: 7239: 7231: 7227: 7219: 7215: 7207: 7203: 7195: 7188: 7180: 7176: 7168: 7164: 7156: 7152: 7144: 7140: 7128: 7124: 7111: 7107: 7095: 7091: 7083: 7079: 7071: 7067: 7055: 7051: 7043: 7036: 7028: 7019: 7011: 7007: 6999: 6995: 6987: 6983: 6975: 6971: 6963: 6959: 6951: 6947: 6939: 6935: 6929:Koivisto (2004) 6927: 6923: 6915: 6911: 6903: 6899: 6891: 6887: 6879: 6872: 6864: 6860: 6852: 6845: 6837: 6833: 6825: 6821: 6813: 6809: 6802: 6798: 6791: 6787: 6780: 6776: 6768: 6764: 6756: 6752: 6739: 6735: 6731: 6689: 6673: 6600:Strong coloring 6524:L(2,1)-coloring 6353: 6351:Other colorings 6331: 6327: 6325: 6322: 6321: 6306: 6300: 6295: 6293:Other colorings 6283: 6236: 6230: 6222:unit disk graph 6194: 6189: 6102: 6099: 6098: 6062: 6049: 6042: 6033: 6032: 6031: 6028: 6025: 6024: 5992:The best known 5971:Brooks' theorem 5947: 5938:message passing 5934: 5916: 5913:(Δ + 5873: 5869: 5865: 5861: 5859: 5856: 5855: 5838: 5818: 5792: 5769: 5755: 5684:symmetric graph 5665: 5613: 5610: 5609: 5589: 5586: 5585: 5539: 5536: 5535: 5519: 5516: 5515: 5495: 5491: 5483: 5480: 5479: 5429: 5373: 5369: 5355: 5349: 5344: 5343: 5341: 5338: 5337: 5315:interval graphs 5288: 5283: 5280: 5279: 5246: 5243: 5242: 5219: 5215: 5213: 5210: 5209: 5192: 5188: 5186: 5183: 5182: 5165: 5161: 5159: 5156: 5155: 5138: 5134: 5132: 5129: 5128: 5111: 5107: 5105: 5102: 5101: 5084: 5080: 5078: 5075: 5074: 5047: 5042: 5039: 5038: 5027: 5025:Greedy coloring 5021: 5019:Greedy coloring 5011:strategies and 4979: 4976: 4975: 4941: 4937: 4916: 4898: 4891: 4888: 4884: 4883: 4881: 4878: 4877: 4789: 4786: 4785: 4781: 4756: 4753: 4752: 4689: 4648: 4645: 4644: 4625: 4600: 4597: 4596: 4553: 4512: 4495: 4492: 4491: 4431: 4426: 4423: 4422: 4416: 4391: 4387: 4379: 4376: 4375: 4355: 4351: 4343: 4340: 4339: 4312: 4308: 4300: 4297: 4296: 4264: 4260: 4252: 4249: 4248: 4193: 4190: 4189: 4180:assignments of 4164: 4160: 4158: 4155: 4154: 4144: 4132:Closed formulas 4124:polynomial time 4100: 4098:Polynomial time 4073:Approximability 3957:Approximability 3795: 3753: 3750: 3749: 3721: 3718: 3717: 3689: 3686: 3685: 3654: 3651: 3650: 3640:crossing number 3539: 3537: 3533: 3516: 3513: 3512: 3451: 3448: 3447: 3444: 3432: 3405:axiom of choice 3348: 3320: 3317: 3316: 3300: 3297: 3296: 3280: 3277: 3276: 3216: 3214: 3211: 3210: 3206:Kőnig's theorem 3152: 3150: 3147: 3146: 3118: 3115: 3114: 3056: 3054: 3051: 3050: 3022: 3019: 3018: 3008: 2963: 2958: 2957: 2955: 2952: 2951: 2934: 2929: 2928: 2926: 2923: 2922: 2900: 2895: 2894: 2892: 2889: 2888: 2830: 2781: 2777: 2760: 2759: 2735: 2731: 2713: 2709: 2707: 2704: 2703: 2653: 2649: 2647: 2644: 2643: 2588: 2587: 2579: 2576: 2575: 2519: 2515: 2513: 2510: 2509: 2490: 2487: 2486: 2460: 2456: 2454: 2451: 2450: 2434: 2431: 2430: 2402: 2399: 2398: 2373: 2367: 2349: 2345: 2343: 2340: 2339: 2323: 2320: 2319: 2312: 2311: 2264: 2260: 2258: 2255: 2254: 2235: 2232: 2231: 2205: 2201: 2195: 2173: 2169: 2167: 2164: 2163: 2147: 2144: 2143: 2117: 2113: 2095: 2091: 2089: 2086: 2085: 2055: 2051: 2050: 2034: 2030: 2029: 2026: 2002: 1998: 1996: 1993: 1992: 1976: 1973: 1972: 1944: 1941: 1940: 1911: 1907: 1905: 1902: 1901: 1885: 1882: 1881: 1821: 1818: 1817: 1792: 1738: 1735: 1734: 1730:Brooks' theorem 1722:Brooks' theorem 1690: 1687: 1686: 1655: 1652: 1651: 1610: 1607: 1606: 1575: 1572: 1571: 1522: 1519: 1518: 1508:greedy coloring 1444: 1441: 1440: 1406: 1403: 1402: 1385: 1384: 1382: 1379: 1378: 1362: 1359: 1358: 1342: 1339: 1338: 1319: 1316: 1315: 1296: 1295: 1293: 1290: 1289: 1225: 1222: 1221: 1188: 1184: 1176: 1173: 1172: 1151: 1147: 1145: 1142: 1141: 1135:edgeless graphs 1091: 1088: 1087: 1081: 1076: 1048: 1043: 1042: 1040: 1037: 1036: 1034: 1030: 1008: 996: 984: 975: 971: 963: 952: 946: 917: 910:chromatic index 905: 898: 894: 890: 879: 873: 823: 803: 799: 795: 778: 772: 742: 738: 734: 713: 709: 703: 671: 667: 663: 649: 622: 618: 610: 606: 602: 587: 523: 513: 507: 504: 498: 491: 480: 473: 468: 464: 461:independent set 452: 446: 439: 434: 422: 421:is used, since 414: 406: 398: 392: 387: 381: 344: 342:Vertex coloring 331: 245:introduced the 182:postulated the 180:Francis Guthrie 174:in the form of 152: 142: 71:vertex coloring 35: 28: 23: 22: 15: 12: 11: 5: 9116: 9106: 9105: 9100: 9095: 9090: 9085: 9080: 9078:Graph coloring 9066: 9065: 9059: 9046: 9034: 9026: 9018: 9002: 9001:External links 8999: 8997: 8996: 8960: 8936: 8908: 8903: 8886: 8875: 8854: 8845: 8840: 8827: 8805: 8796: 8787: 8782: 8761: 8756: 8731: 8726: 8701: 8669: 8635: 8633:, vol. 20 8626: 8579: 8565: 8537: 8525:(2): 161–162, 8504: 8500:10.1.1.95.4268 8486: 8481: 8468: 8449:(1): 193–201, 8433: 8420: 8397: 8392: 8377: 8356: 8331: 8318: 8294: 8289: 8276: 8271: 8256: 8251: 8238: 8221:(1): 183–189, 8206: 8201: 8188: 8150: 8133:(4): 718–720, 8120: 8100: 8091:(4): 434–446, 8071: 8044:(7): 908–929, 8024: 8011: 7989:Stockmeyer, L. 7985:Johnson, D. S. 7977: 7972: 7958:Johnson, D. S. 7950: 7945: 7915: 7896:(3): 455–457, 7883: 7850: 7823: 7808: 7797:(3): 289–293, 7784: 7752: 7741: 7717: 7704: 7681: 7672:(6): 547–556, 7661: 7652: 7647: 7614: 7558: 7533:(2): 194–197, 7517: 7498:(4): 251–256, 7482: 7473:(2): 546–563, 7460: 7409: 7396: 7353: 7351: 7348: 7346: 7345: 7333: 7321: 7309: 7297: 7285: 7281:Chaitin (1982) 7273: 7261: 7249: 7237: 7225: 7213: 7201: 7186: 7174: 7162: 7150: 7138: 7122: 7105: 7089: 7077: 7065: 7049: 7034: 7017: 7005: 6993: 6981: 6969: 6957: 6945: 6933: 6921: 6909: 6897: 6885: 6883:, p. 550. 6870: 6858: 6843: 6831: 6819: 6807: 6796: 6785: 6774: 6762: 6750: 6732: 6730: 6727: 6726: 6725: 6720: 6715: 6710: 6705: 6700: 6695: 6693:Critical graph 6688: 6685: 6670: 6669: 6665: 6664: 6661: 6656: 6649: 6644: 6637: 6632: 6629: 6627:Total coloring 6624: 6618: 6613: 6610: 6605: 6602: 6597: 6591: 6586: 6583: 6578: 6575: 6570: 6560: 6555: 6552: 6550:Radio coloring 6547: 6544: 6539: 6536: 6529: 6528: 6527: 6512: 6507: 6504: 6499: 6496: 6491: 6488: 6483: 6476: 6471: 6468: 6463: 6460: 6455: 6452: 6447: 6444: 6439: 6436: 6434:Exact coloring 6431: 6428: 6423: 6420: 6415: 6412: 6407: 6404: 6399: 6396: 6391: 6388: 6383: 6380: 6375: 6372: 6367: 6364: 6354: 6352: 6349: 6334: 6330: 6302:Main article: 6299: 6296: 6294: 6291: 6282: 6279: 6232:Main article: 6229: 6226: 6214:interval graph 6193: 6190: 6188: 6185: 6134:rational point 6121: 6118: 6115: 6112: 6109: 6106: 6074: 6071: 6065: 6059: 6056: 6052: 6048: 6045: 6041: 6036: 5946: 5943: 5933: 5930: 5888: 5883: 5880: 5877: 5872: 5868: 5864: 5664: 5661: 5629: 5626: 5623: 5620: 5617: 5593: 5573: 5570: 5567: 5564: 5561: 5558: 5555: 5552: 5549: 5546: 5543: 5523: 5503: 5498: 5494: 5490: 5487: 5428: 5425: 5396: 5393: 5390: 5387: 5384: 5381: 5376: 5372: 5368: 5365: 5362: 5352: 5311:chordal graphs 5295: 5291: 5287: 5259: 5256: 5253: 5250: 5228: 5225: 5222: 5218: 5195: 5191: 5168: 5164: 5141: 5137: 5114: 5110: 5087: 5083: 5054: 5050: 5046: 5023:Main article: 5020: 5017: 5005:spanning trees 4992: 4989: 4986: 4983: 4955: 4950: 4947: 4944: 4940: 4936: 4933: 4930: 4925: 4922: 4919: 4914: 4908: 4902: 4897: 4894: 4887: 4817: 4814: 4811: 4808: 4805: 4802: 4799: 4796: 4793: 4769: 4766: 4763: 4760: 4741: 4740: 4729: 4726: 4723: 4720: 4717: 4714: 4711: 4708: 4705: 4702: 4699: 4696: 4692: 4688: 4685: 4682: 4679: 4676: 4673: 4670: 4667: 4664: 4661: 4658: 4655: 4652: 4613: 4610: 4607: 4604: 4581: 4580: 4569: 4566: 4563: 4560: 4556: 4552: 4549: 4546: 4543: 4540: 4537: 4534: 4531: 4528: 4525: 4522: 4519: 4511: 4508: 4505: 4502: 4499: 4441: 4438: 4434: 4430: 4415: 4412: 4399: 4394: 4390: 4386: 4383: 4363: 4358: 4354: 4350: 4347: 4323: 4320: 4315: 4311: 4307: 4304: 4272: 4267: 4263: 4259: 4256: 4221: 4218: 4215: 4212: 4209: 4206: 4203: 4200: 4197: 4167: 4163: 4143: 4140: 4120:perfect graphs 4099: 4096: 4093: 4092: 4085: 4081: 4080: 4074: 4070: 4069: 4064: 4060: 4059: 4052: 4048: 4047: 4043:-colorings of 4025: 4021: 4020: 4006: 4002: 4001: 3998: 3994: 3993: 3989: 3988: 3978: 3974: 3973: 3958: 3954: 3953: 3948: 3944: 3943: 3936: 3932: 3931: 3920: 3916: 3915: 3912: 3908: 3907: 3903: 3902: 3899: 3895: 3894: 3889: 3888:Reduction from 3885: 3884: 3879: 3875: 3874: 3867: 3863: 3862: 3851: 3847: 3846: 3832: 3828: 3827: 3820: 3816: 3815: 3811: 3810: 3802: 3801: 3800:Graph coloring 3794: 3791: 3778: 3775: 3772: 3769: 3766: 3763: 3760: 3757: 3737: 3734: 3731: 3728: 3725: 3705: 3702: 3699: 3696: 3693: 3673: 3670: 3667: 3664: 3661: 3658: 3622:vertices as a 3616:complete graph 3585: 3581: 3576: 3572: 3569: 3566: 3563: 3560: 3557: 3554: 3551: 3548: 3545: 3542: 3536: 3532: 3529: 3526: 3523: 3520: 3500: 3497: 3494: 3491: 3488: 3485: 3482: 3479: 3476: 3473: 3470: 3467: 3464: 3461: 3458: 3455: 3443: 3440: 3439: 3438: 3430: 3416: 3407:. This is the 3390:infinite graph 3366:; this is the 3358:for which the 3350:A graph has a 3347: 3344: 3343: 3342: 3330: 3327: 3324: 3304: 3284: 3264: 3263: 3247: 3244: 3241: 3238: 3235: 3232: 3229: 3226: 3222: 3219: 3198: 3197: 3186: 3183: 3180: 3177: 3174: 3171: 3168: 3165: 3162: 3158: 3155: 3131: 3128: 3125: 3122: 3111: 3110: 3099: 3096: 3093: 3090: 3087: 3084: 3081: 3078: 3075: 3072: 3069: 3066: 3062: 3059: 3035: 3032: 3029: 3026: 3007: 3004: 3003: 3002: 2966: 2961: 2937: 2932: 2903: 2898: 2885:Burling (1965) 2877: 2876: 2838:Grötzsch graph 2829: 2826: 2825: 2824: 2813: 2810: 2807: 2804: 2801: 2798: 2795: 2792: 2789: 2784: 2780: 2776: 2773: 2767: 2764: 2758: 2755: 2752: 2749: 2746: 2743: 2738: 2734: 2730: 2727: 2724: 2721: 2716: 2712: 2697: 2696: 2685: 2682: 2679: 2676: 2673: 2670: 2667: 2664: 2661: 2656: 2652: 2631: 2630: 2619: 2616: 2613: 2610: 2607: 2604: 2601: 2595: 2592: 2586: 2583: 2563: 2562: 2551: 2548: 2545: 2542: 2539: 2536: 2533: 2530: 2527: 2522: 2518: 2494: 2474: 2471: 2468: 2463: 2459: 2438: 2429:is an edge in 2418: 2415: 2412: 2409: 2406: 2382: 2379: 2376: 2372: 2366: 2363: 2358: 2355: 2352: 2348: 2327: 2308: 2307: 2296: 2293: 2290: 2287: 2284: 2281: 2278: 2275: 2272: 2267: 2263: 2239: 2219: 2216: 2213: 2208: 2204: 2198: 2194: 2190: 2187: 2184: 2181: 2176: 2172: 2151: 2131: 2128: 2125: 2120: 2116: 2112: 2109: 2106: 2103: 2098: 2094: 2069: 2066: 2063: 2058: 2054: 2048: 2045: 2042: 2037: 2033: 2025: 2022: 2019: 2016: 2013: 2010: 2005: 2001: 1980: 1960: 1957: 1954: 1951: 1948: 1928: 1925: 1920: 1917: 1914: 1910: 1889: 1872:clique problem 1868:perfect graphs 1864: 1863: 1852: 1849: 1846: 1843: 1840: 1837: 1834: 1831: 1828: 1825: 1791: 1788: 1787: 1786: 1766: 1763: 1760: 1757: 1754: 1751: 1748: 1745: 1742: 1709: 1706: 1703: 1700: 1697: 1694: 1674: 1671: 1668: 1665: 1662: 1659: 1635: 1632: 1629: 1626: 1623: 1620: 1617: 1614: 1594: 1591: 1588: 1585: 1582: 1579: 1568: 1567: 1556: 1553: 1550: 1547: 1544: 1541: 1538: 1535: 1532: 1529: 1526: 1481: 1478: 1475: 1472: 1469: 1466: 1463: 1460: 1457: 1454: 1451: 1448: 1428: 1425: 1422: 1419: 1416: 1413: 1410: 1388: 1366: 1346: 1323: 1299: 1286: 1285: 1274: 1271: 1268: 1265: 1262: 1259: 1256: 1253: 1250: 1247: 1244: 1241: 1238: 1235: 1232: 1229: 1202: 1199: 1196: 1191: 1187: 1183: 1180: 1154: 1150: 1139:complete graph 1131: 1130: 1119: 1116: 1113: 1110: 1107: 1104: 1101: 1098: 1095: 1080: 1077: 1075: 1072: 1051: 1046: 1007: 1004: 995: 992: 983: 980: 955:Total coloring 950:Total coloring 948:Main article: 945: 944:Total coloring 942: 875:Main article: 872: 869: 866: 865: 821: 819:Petersen graph 815: 814: 801: 797: 789: 788: 776: 765: 764: 740: 736: 732:Complete graph 728: 727: 711: 707: 605:-colorings of 582: 581: 578: 575: 572: 569: 566: 562: 561: 558: 555: 552: 549: 546: 519:Main article: 511: 502: 490: 487: 401:is called its 343: 340: 330: 327: 236:Wolfgang Haken 141: 138: 59:graph labeling 55:graph coloring 43:Petersen graph 26: 9: 6: 4: 3: 2: 9115: 9104: 9101: 9099: 9096: 9094: 9091: 9089: 9086: 9084: 9081: 9079: 9076: 9075: 9073: 9063: 9060: 9057: 9053: 9050: 9047: 9045: 9041: 9038: 9035: 9032: 9031: 9027: 9024: 9023: 9019: 9016: 9015: 9010: 9009: 9005: 9004: 8994: 8991: 8987: 8982: 8978: 8974: 8970: 8966: 8961: 8957: 8952: 8948: 8944: 8943: 8937: 8933: 8928: 8924: 8920: 8919: 8909: 8906: 8900: 8897:, CRC Press, 8895: 8894: 8887: 8883: 8882: 8876: 8872: 8868: 8855: 8851: 8846: 8843: 8841:0-13-227828-6 8837: 8833: 8828: 8824: 8819: 8815: 8811: 8806: 8802: 8797: 8793: 8788: 8785: 8779: 8775: 8771: 8767: 8762: 8759: 8753: 8749: 8745: 8741: 8737: 8732: 8729: 8727:3-540-60573-8 8723: 8719: 8715: 8711: 8707: 8702: 8699: 8695: 8691: 8687: 8683: 8679: 8670: 8666: 8661: 8656: 8651: 8647: 8643: 8642: 8636: 8632: 8627: 8624: 8620: 8616: 8612: 8608: 8604: 8600: 8596: 8592: 8585: 8580: 8576: 8572: 8568: 8562: 8558: 8554: 8550: 8546: 8542: 8538: 8533: 8528: 8524: 8520: 8519:Colloq. Math. 8513: 8509: 8508:Mycielski, J. 8505: 8501: 8496: 8492: 8487: 8484: 8482:0-521-80340-3 8478: 8474: 8469: 8466: 8462: 8457: 8452: 8448: 8444: 8443: 8438: 8434: 8431: 8427: 8423: 8417: 8413: 8409: 8405: 8404: 8398: 8395: 8389: 8385: 8384: 8378: 8369: 8362: 8357: 8354: 8350: 8346: 8342: 8341: 8336: 8332: 8329: 8325: 8321: 8315: 8311: 8307: 8303: 8302: 8295: 8292: 8290:0-8218-3458-4 8286: 8282: 8277: 8274: 8272:952-10-1578-0 8268: 8264: 8263: 8257: 8254: 8252:0-201-89684-2 8248: 8244: 8239: 8236: 8232: 8228: 8224: 8220: 8216: 8212: 8207: 8204: 8202:0-471-02865-7 8198: 8194: 8189: 8186: 8182: 8178: 8174: 8170: 8166: 8162: 8158: 8157: 8151: 8148: 8144: 8140: 8136: 8132: 8128: 8127: 8121: 8118: 8114: 8110: 8106: 8101: 8098: 8094: 8090: 8086: 8085: 8080: 8076: 8072: 8069: 8065: 8061: 8057: 8052: 8047: 8043: 8039: 8038: 8033: 8029: 8025: 8022: 8018: 8014: 8012:9781450374231 8008: 8004: 8000: 7996: 7995: 7990: 7986: 7982: 7978: 7975: 7973:0-7167-1045-5 7969: 7965: 7964: 7959: 7955: 7951: 7948: 7942: 7937: 7932: 7928: 7924: 7920: 7916: 7913: 7909: 7904: 7899: 7895: 7891: 7890: 7889:Can. J. Math. 7884: 7881: 7877: 7872: 7867: 7863: 7859: 7855: 7851: 7848: 7844: 7840: 7836: 7829: 7824: 7821: 7817: 7813: 7809: 7805: 7800: 7796: 7792: 7791: 7785: 7782: 7778: 7773: 7768: 7764: 7760: 7759: 7753: 7749: 7748: 7742: 7738: 7733: 7729: 7725: 7724: 7718: 7715: 7711: 7707: 7705:0-89791-074-5 7701: 7697: 7693: 7689: 7688: 7682: 7679: 7675: 7671: 7667: 7662: 7658: 7653: 7650: 7644: 7639: 7634: 7629: 7624: 7620: 7615: 7612: 7609: 7598:on 2016-03-10 7594: 7590: 7586: 7582: 7578: 7571: 7567: 7563: 7559: 7556: 7552: 7548: 7544: 7540: 7536: 7532: 7528: 7527: 7522: 7521:Brooks, R. L. 7518: 7515: 7511: 7506: 7501: 7497: 7493: 7492: 7487: 7483: 7480: 7476: 7472: 7468: 7467: 7461: 7458: 7454: 7450: 7446: 7441: 7436: 7432: 7428: 7427: 7420: 7415: 7410: 7407: 7403: 7399: 7393: 7389: 7385: 7380: 7375: 7371: 7370: 7355: 7354: 7342: 7337: 7330: 7325: 7318: 7313: 7306: 7301: 7294: 7289: 7282: 7277: 7270: 7265: 7258: 7253: 7246: 7245:Holyer (1981) 7241: 7234: 7229: 7222: 7217: 7210: 7205: 7198: 7193: 7191: 7183: 7178: 7171: 7166: 7159: 7154: 7147: 7146:Dailey (1980) 7142: 7135: 7131: 7126: 7119: 7115: 7109: 7102: 7098: 7093: 7086: 7081: 7074: 7069: 7062: 7058: 7053: 7046: 7041: 7039: 7031: 7026: 7024: 7022: 7014: 7013:Brélaz (1979) 7009: 7002: 6997: 6990: 6985: 6978: 6973: 6966: 6961: 6954: 6949: 6942: 6937: 6930: 6925: 6918: 6913: 6906: 6901: 6894: 6893:Lawler (1976) 6889: 6882: 6877: 6875: 6867: 6862: 6855: 6850: 6848: 6840: 6835: 6828: 6823: 6816: 6815:Brooks (1941) 6811: 6805: 6800: 6794: 6789: 6783: 6778: 6771: 6766: 6759: 6754: 6747: 6746:Kubale (2004) 6743: 6737: 6733: 6724: 6721: 6719: 6716: 6714: 6711: 6709: 6706: 6704: 6701: 6699: 6696: 6694: 6691: 6690: 6684: 6682: 6678: 6677:signed graphs 6668: 6662: 6660: 6659:Weak coloring 6657: 6654: 6653:triangle-free 6650: 6648: 6645: 6642: 6638: 6636: 6633: 6630: 6628: 6625: 6623: 6619: 6617: 6614: 6611: 6609: 6606: 6603: 6601: 6598: 6596: 6592: 6590: 6589:Star coloring 6587: 6584: 6582: 6579: 6576: 6574: 6571: 6569: 6565: 6561: 6559: 6558:Rank coloring 6556: 6553: 6551: 6548: 6545: 6543: 6542:Path coloring 6540: 6537: 6535: 6532: 6531: 6530: 6525: 6521: 6517: 6513: 6511: 6508: 6505: 6503: 6500: 6497: 6495: 6494:List coloring 6492: 6489: 6487: 6484: 6481: 6477: 6475: 6472: 6469: 6467: 6464: 6461: 6459: 6456: 6453: 6451: 6448: 6445: 6443: 6440: 6437: 6435: 6432: 6429: 6427: 6424: 6421: 6419: 6416: 6413: 6411: 6408: 6405: 6403: 6400: 6397: 6395: 6392: 6389: 6387: 6384: 6381: 6379: 6376: 6373: 6371: 6368: 6365: 6363: 6360: 6359: 6358: 6357: 6348: 6332: 6328: 6319: 6315: 6314:Ramsey theory 6311: 6305: 6304:Ramsey theory 6298:Ramsey theory 6290: 6288: 6278: 6276: 6272: 6268: 6263: 6261: 6257: 6253: 6249: 6245: 6241: 6235: 6225: 6223: 6219: 6215: 6210: 6208: 6203: 6199: 6184: 6182: 6178: 6174: 6168: 6166: 6163: = 6162: 6158: 6154: 6150: 6146: 6142: 6138: 6135: 6116: 6113: 6110: 6104: 6096: 6091: 6089: 6072: 6069: 6054: 6050: 6046: 6039: 6022: 6017: 6015: 6011: 6007: 6003: 5999: 5995: 5990: 5988: 5984: 5980: 5976: 5972: 5968: 5967:planar graphs 5964: 5960: 5956: 5952: 5942: 5939: 5929: 5927: 5926:Linial (1992) 5923: 5919: 5912: 5908: 5903: 5886: 5881: 5878: 5875: 5870: 5866: 5862: 5853: 5849: 5845: 5841: 5834: 5829: 5825: 5821: 5814: 5809: 5807: 5803: 5799: 5795: 5788: 5787:Linial (1992) 5784: 5780: 5779:constant-time 5776: 5772: 5766:The function 5764: 5762: 5758: 5751: 5747: 5743: 5739: 5735: 5731: 5727: 5723: 5718: 5716: 5711: 5709: 5705: 5701: 5697: 5693: 5689: 5688:deterministic 5685: 5680: 5678: 5674: 5670: 5660: 5658: 5654: 5650: 5646: 5641: 5624: 5621: 5615: 5607: 5591: 5568: 5565: 5562: 5556: 5553: 5550: 5541: 5521: 5496: 5492: 5485: 5476: 5473: 5469: 5464: 5462: 5457: 5453: 5449: 5445: 5440: 5438: 5434: 5424: 5422: 5421:Grundy number 5417: 5415: 5410: 5391: 5388: 5385: 5382: 5374: 5370: 5363: 5350: 5335: 5330: 5328: 5324: 5320: 5316: 5312: 5307: 5293: 5289: 5285: 5277: 5273: 5254: 5248: 5226: 5223: 5220: 5216: 5193: 5189: 5166: 5162: 5139: 5135: 5112: 5108: 5085: 5081: 5072: 5052: 5048: 5044: 5036: 5031: 5026: 5016: 5014: 5010: 5006: 4987: 4981: 4973: 4970:vertices and 4969: 4948: 4945: 4942: 4938: 4931: 4928: 4923: 4920: 4917: 4912: 4906: 4900: 4895: 4892: 4885: 4875: 4871: 4866: 4864: 4860: 4856: 4852: 4848: 4844: 4840: 4836: 4832: 4812: 4809: 4806: 4803: 4800: 4797: 4791: 4767: 4764: 4761: 4758: 4750: 4746: 4724: 4721: 4718: 4712: 4709: 4703: 4700: 4697: 4694: 4690: 4686: 4680: 4677: 4671: 4668: 4665: 4662: 4659: 4656: 4650: 4643: 4642: 4641: 4638: 4636: 4632: 4611: 4608: 4605: 4602: 4594: 4590: 4586: 4561: 4558: 4554: 4550: 4544: 4541: 4535: 4532: 4529: 4526: 4520: 4509: 4503: 4497: 4490: 4489: 4488: 4486: 4481: 4479: 4475: 4471: 4467: 4463: 4459: 4455: 4439: 4436: 4432: 4428: 4421: 4411: 4392: 4388: 4381: 4356: 4352: 4345: 4337: 4318: 4313: 4309: 4302: 4294: 4290: 4286: 4265: 4261: 4254: 4246: 4242: 4238: 4233: 4219: 4216: 4213: 4210: 4207: 4204: 4201: 4198: 4195: 4187: 4183: 4165: 4161: 4152: 4148: 4139: 4135: 4133: 4129: 4125: 4121: 4117: 4113: 4109: 4105: 4090: 4086: 4082: 4078: 4075: 4071: 4068: 4065: 4061: 4057: 4053: 4049: 4046: 4042: 4038: 4034: 4030: 4026: 4022: 4019: 4015: 4011: 4007: 4003: 3999: 3995: 3990: 3987: 3983: 3979: 3975: 3971: 3967: 3963: 3959: 3955: 3952: 3949: 3945: 3941: 3937: 3933: 3929: 3925: 3921: 3917: 3913: 3909: 3904: 3900: 3898:Garey–Johnson 3896: 3893: 3890: 3886: 3883: 3880: 3876: 3872: 3868: 3864: 3860: 3856: 3852: 3848: 3845: 3841: 3837: 3833: 3829: 3825: 3821: 3817: 3812: 3808: 3803: 3798: 3790: 3776: 3773: 3767: 3764: 3761: 3755: 3729: 3726: 3697: 3694: 3668: 3665: 3662: 3656: 3648: 3643: 3641: 3637: 3633: 3629: 3625: 3621: 3617: 3613: 3609: 3605: 3604:open problems 3601: 3596: 3583: 3579: 3574: 3570: 3567: 3561: 3552: 3546: 3540: 3534: 3530: 3524: 3518: 3498: 3495: 3489: 3480: 3474: 3468: 3465: 3459: 3453: 3442:Open problems 3436: 3429: 3425: 3421: 3417: 3414: 3410: 3406: 3402: 3398: 3394: 3391: 3387: 3386: 3385: 3382: 3380: 3375: 3373: 3369: 3365: 3361: 3357: 3353: 3328: 3325: 3274: 3273: 3269: 3268: 3267: 3262:is bipartite. 3261: 3242: 3233: 3227: 3220: 3217: 3209: 3207: 3203: 3202: 3201: 3184: 3178: 3169: 3163: 3156: 3153: 3145: 3144: 3143: 3126: 3097: 3088: 3082: 3076: 3073: 3067: 3060: 3057: 3049: 3048: 3047: 3030: 3024: 3017: 3013: 3000: 2996: 2993: 2992: 2991: 2989: 2984: 2982: 2964: 2935: 2919: 2901: 2886: 2882: 2874: 2870: 2866: 2862: 2858: 2854: 2850: 2847: 2846: 2845: 2843: 2839: 2835: 2811: 2805: 2799: 2796: 2790: 2782: 2778: 2774: 2762: 2753: 2750: 2744: 2736: 2732: 2728: 2722: 2714: 2710: 2702: 2701: 2700: 2683: 2677: 2671: 2668: 2662: 2654: 2650: 2642: 2641: 2640: 2638: 2636: 2617: 2611: 2605: 2602: 2590: 2581: 2574: 2573: 2572: 2570: 2568: 2567:Lovász number 2549: 2543: 2537: 2534: 2528: 2520: 2516: 2508: 2507: 2506: 2505:exists. Then 2492: 2469: 2461: 2457: 2436: 2413: 2410: 2407: 2380: 2377: 2374: 2370: 2364: 2361: 2356: 2353: 2350: 2346: 2325: 2317: 2294: 2288: 2282: 2279: 2273: 2265: 2261: 2253: 2252: 2251: 2237: 2214: 2206: 2202: 2196: 2188: 2182: 2174: 2170: 2149: 2126: 2114: 2110: 2104: 2092: 2064: 2052: 2043: 2031: 2023: 2020: 2017: 2011: 2003: 1999: 1978: 1955: 1952: 1949: 1926: 1923: 1918: 1915: 1912: 1908: 1887: 1879: 1875: 1873: 1869: 1850: 1844: 1838: 1835: 1829: 1823: 1816: 1815: 1814: 1812: 1808: 1804: 1800: 1795: 1784: 1780: 1761: 1752: 1746: 1740: 1733: 1731: 1727: 1726: 1725: 1723: 1707: 1704: 1698: 1672: 1669: 1663: 1657: 1649: 1633: 1630: 1627: 1624: 1618: 1592: 1589: 1583: 1577: 1554: 1551: 1545: 1536: 1530: 1524: 1517: 1516: 1515: 1513: 1509: 1504: 1502: 1498: 1493: 1476: 1470: 1467: 1458: 1452: 1446: 1420: 1414: 1408: 1364: 1344: 1336: 1335: 1321: 1312:of graphs is 1272: 1269: 1266: 1263: 1257: 1254: 1248: 1242: 1233: 1227: 1220: 1219: 1218: 1216: 1200: 1197: 1189: 1185: 1178: 1170: 1152: 1148: 1140: 1136: 1117: 1114: 1111: 1105: 1099: 1096: 1093: 1086: 1085: 1084: 1071: 1069: 1049: 1027: 1025: 1021: 1017: 1013: 1003: 1001: 991: 989: 988:Face coloring 982:Face coloring 979: 967: 960: 956: 951: 941: 939: 935: 931: 927: 926:Tait coloring 921: 915: 911: 903: 888: 884: 883:edge coloring 878: 877:Edge coloring 871:Edge coloring 862: 858: 854: 850: 846: 842: 838: 834: 830: 826: 822: 820: 817: 816: 811: 807: 802: 794: 791: 790: 785: 781: 777: 770: 767: 766: 761: 757: 753: 749: 745: 741: 733: 730: 729: 724: 720: 716: 712: 706: 701: 700: 694: 691: 687: 683: 679: 675: 660: 656: 652: 648:, and indeed 645: 641: 637: 633: 629: 625: 616: 598: 594: 590: 579: 576: 573: 570: 567: 564: 563: 559: 556: 553: 550: 547: 544: 543: 540: 537: 533: 528: 522: 510: 501: 495: 486: 484: 477: 462: 458: 450: 443: 437:-coloring is 432: 426: 418: 413:. Sometimes 410: 404: 396: 384: 382:{1, 2, 3, …}. 380: 376: 372: 368: 363: 361: 357: 353: 349: 335: 326: 324: 320: 316: 312: 311: 305: 303: 299: 295: 291: 287: 283: 279: 275: 271: 267: 262: 260: 256: 252: 248: 244: 239: 237: 233: 232:Kenneth Appel 228: 224: 220: 215: 213: 212:Royal Society 209: 205: 201: 200:Arthur Cayley 197: 193: 189: 185: 181: 177: 173: 172:planar graphs 165: 161: 160:United States 158:A map of the 156: 151: 147: 137: 136: 134: 128: 126: 120: 118: 113: 109: 104: 102: 98: 94: 88: 86: 82: 81:face coloring 78: 77: 76:edge coloring 72: 68: 64: 60: 56: 52: 44: 39: 33: 32:Edge coloring 19: 9083:Graph theory 9029: 9021: 9012: 9007: 8985: 8972: 8969:Mat. Sbornik 8968: 8946: 8940: 8916: 8892: 8880: 8870: 8849: 8831: 8816:(1): 85–86, 8813: 8809: 8800: 8791: 8765: 8739: 8705: 8681: 8677: 8645: 8644:, Series B, 8639: 8630: 8594: 8590: 8548: 8522: 8518: 8490: 8472: 8446: 8440: 8402: 8382: 8371:, retrieved 8367: 8347:(3): 66–67, 8344: 8338: 8335:Lawler, E.L. 8298: 8280: 8261: 8242: 8218: 8214: 8192: 8163:(1): 35–53, 8160: 8154: 8130: 8124: 8108: 8104: 8088: 8082: 8041: 8035: 7993: 7981:Garey, M. R. 7961: 7954:Garey, M. R. 7922: 7893: 7887: 7861: 7857: 7841:(2): 60–63, 7838: 7834: 7819: 7815: 7794: 7788: 7762: 7756: 7745: 7730:(1): 32–53, 7727: 7721: 7685: 7669: 7665: 7656: 7618: 7610: 7608:Indag. Math. 7607: 7600:, retrieved 7593:the original 7580: 7576: 7530: 7524: 7495: 7489: 7470: 7464: 7430: 7424: 7418: 7414:Eppstein, D. 7412:Beigel, R.; 7366: 7341:Lewis (2021) 7336: 7329:Lewis (2021) 7324: 7317:Lewis (2021) 7312: 7305:Lewis (2021) 7300: 7293:Lewis (2021) 7288: 7276: 7264: 7252: 7240: 7228: 7216: 7204: 7177: 7165: 7153: 7141: 7125: 7108: 7092: 7080: 7068: 7052: 7030:Lewis (2021) 7008: 6996: 6984: 6972: 6965:Zamir (2021) 6960: 6948: 6936: 6924: 6917:Knuth (1997) 6912: 6905:Yates (1937) 6900: 6888: 6866:Erdős (1959) 6861: 6834: 6822: 6810: 6804:Zhang (1997) 6799: 6793:Tutte (1954) 6788: 6782:Tutte (1949) 6777: 6772:, p. 2. 6765: 6753: 6741: 6736: 6674: 6666: 6621: 6581:Sum coloring 6567: 6563: 6519: 6515: 6309: 6307: 6284: 6274: 6270: 6266: 6264: 6237: 6211: 6206: 6201: 6195: 6187:Applications 6176: 6172: 6169: 6156: 6152: 6144: 6140: 6136: 6092: 6087: 6020: 6018: 6009: 6005: 6001: 5997: 5991: 5978: 5974: 5962: 5958: 5954: 5948: 5935: 5921: 5910: 5904: 5847: 5843: 5832: 5823: 5812: 5810: 5805: 5801: 5797: 5782: 5778: 5765: 5760: 5749: 5745: 5741: 5737: 5733: 5721: 5719: 5714: 5712: 5707: 5703: 5699: 5695: 5691: 5681: 5666: 5657:wheel graphs 5642: 5477: 5465: 5460: 5441: 5430: 5423:of a graph. 5418: 5416:algorithms. 5413: 5331: 5308: 5275: 5068: 5034: 4971: 4967: 4869: 4867: 4858: 4854: 4850: 4846: 4842: 4838: 4834: 4830: 4748: 4744: 4742: 4639: 4634: 4630: 4592: 4588: 4585:Zykov (1949) 4582: 4482: 4477: 4473: 4469: 4465: 4461: 4457: 4453: 4417: 4335: 4292: 4244: 4234: 4185: 4181: 4150: 4145: 4136: 4101: 4055: 4051:Running time 4044: 4040: 4039:) of proper 4036: 4032: 4028: 4017: 4013: 4009: 3981: 3969: 3965: 3964: (log 3961: 3939: 3927: 3923: 3906:Optimisation 3870: 3866:Running time 3858: 3854: 3843: 3839: 3835: 3823: 3646: 3644: 3635: 3619: 3611: 3597: 3445: 3435:Fawcett 1978 3427: 3423: 3419: 3400: 3396: 3392: 3383: 3376: 3363: 3360:longest path 3351: 3349: 3270: 3265: 3259: 3204: 3199: 3112: 3011: 3009: 2994: 2985: 2878: 2848: 2842:Mycielskians 2831: 2698: 2633: 2632: 2565: 2564: 2310: 2309: 1877: 1876: 1865: 1810: 1806: 1798: 1796: 1793: 1782: 1778: 1728: 1724:states that 1569: 1505: 1499:, including 1494: 1314: 1287: 1214: 1168: 1132: 1082: 1028: 1011: 1009: 997: 987: 985: 965: 958: 954: 953: 925: 919: 913: 909: 886: 882: 880: 860: 856: 852: 848: 844: 840: 836: 832: 828: 824: 809: 808:– 1) + (-1)( 805: 783: 779: 759: 755: 751: 747: 743: 722: 718: 714: 704: 689: 685: 681: 677: 673: 661: 654: 650: 643: 639: 635: 631: 627: 623: 596: 592: 588: 585: 535: 531: 526: 524: 508: 499: 479: 472: 456: 445: 444:, and it is 438: 424: 416: 408: 402: 391: 385: 374: 370: 366: 364: 351: 347: 345: 319:Zykov (1949) 308: 306: 269: 266:Claude Berge 263: 240: 226: 216: 208:Alfred Kempe 176:map coloring 169: 130: 129: 121: 105: 89: 85:planar graph 80: 74: 70: 54: 51:graph theory 48: 8949:: 103–128, 8648:(5): 6–10, 7919:Fomin, F.V. 7854:Erdős, Paul 7583:: 371–373, 7269:Marx (2004) 7101:Kuhn (2009) 7059:, see also 6977:Wilf (1986) 6760:, Chap. 33. 6740:M. Kubale, 6681:gain graphs 6573:Subcoloring 6277:registers. 6139:except for 6086:colors for 5951:NP-complete 5730:Uzi Vishkin 5272:crown graph 4452:of a graph 4420:contraction 4414:Contraction 4108:linear time 4067:#P-complete 4027:The number 3882:NP-complete 3634:that among 1801:contains a 1068:permutation 970:of a graph 930:cubic graph 457:color class 255:W. T. Tutte 101:pedagogical 9072:Categories 9030:CoLoRaTiOn 8684:(3): 2–3, 8601:: 97–100, 8437:Linial, N. 8373:2016-03-03 8051:cs/0605140 8032:Jerrum, M. 7628:1811.00970 7602:2009-05-16 7486:Brélaz, D. 7440:cs/0006046 7350:References 6616:T-coloring 6394:Cocoloring 6378:B-coloring 6192:Scheduling 5977:> 3, a 5748:-cycle in 5740:(log 4184:colors to 4063:Complexity 3968:)(log log 3947:Complexity 3878:Complexity 3793:Algorithms 3200:Moreover, 3016:line graph 1648:odd cycles 1074:Properties 938:bridgeless 692:) > 0}. 615:polynomial 483:-colorable 463:. Thus, a 449:-chromatic 442:-colorable 290:Chudnovsky 144:See also: 117:finite set 93:line graph 8655:1209.1595 8615:0178-2770 8495:CiteSeerX 8451:CiteSeerX 8235:0304-3975 8185:121454726 8111:: 19–23, 8021:207693360 7912:123812465 7880:122784453 7864:: 34–38, 7765:(4): 90, 7566:Erdős, P. 7555:209835194 7379:0812.1379 7365:) time", 7112:E.g. see 6289:puzzles. 6105:χ 6070:− 6058:⌋ 6044:⌊ 5879:⁡ 5649:bipartite 5566:⁡ 5357: min 5249:χ 5224:− 4801:− 4784:removed. 4762:− 4660:− 4545:χ 4521:χ 4498:χ 4217:− 4208:… 4104:bipartite 3984:) unless 3930:vertices. 3826:-coloring 3774:≠ 3748:and that 3733:∞ 3701:∞ 3556:Δ 3541:ω 3531:≤ 3519:χ 3484:Δ 3481:≤ 3469:χ 3466:≤ 3454:ω 3323:Δ 3303:Δ 3283:Δ 3237:Δ 3218:χ 3173:Δ 3170:≥ 3154:χ 3121:Δ 3077:χ 3058:χ 2981:χ-bounded 2800:χ 2797:≤ 2779:χ 2775:≤ 2766:¯ 2754:ϑ 2751:≤ 2733:χ 2729:≤ 2711:χ 2672:χ 2669:≤ 2651:χ 2606:χ 2603:≤ 2594:¯ 2582:ϑ 2538:χ 2535:≤ 2517:χ 2458:χ 2449:. Define 2397:whenever 2378:− 2365:− 2362:≤ 2283:χ 2280:≤ 2262:χ 2203:χ 2171:χ 2162:. Define 2115:λ 2093:λ 2053:λ 2032:λ 2024:− 2000:χ 1991:. Define 1939:whenever 1839:ω 1836:≥ 1824:χ 1781:, unless 1756:Δ 1753:≤ 1741:χ 1693:Δ 1658:χ 1631:− 1613:Δ 1578:χ 1540:Δ 1537:≤ 1525:χ 1471:ω 1453:ω 1415:ω 1322:χ 1264:≤ 1255:− 1243:χ 1228:χ 1179:χ 1112:≤ 1100:χ 1097:≤ 902:matchings 775:vertices 702:Triangle 395:-coloring 304:in 2002. 294:Robertson 264:In 1960, 241:In 1912, 217:In 1890, 198:in 1852. 9052:Archived 9040:Archived 8988:, 1952, 8623:17661948 8510:(1955), 8430:57188465 8147:13131049 8068:53304001 7960:(1979), 7781:15748200 7714:16872867 7568:(1951), 7514:14838769 7421:(1.3289) 7406:13446345 6687:See also 6655:subgraph 6310:improper 6240:compiler 6207:makespan 6202:conflict 5808:-cycle. 5785:-cycle. 5514:, where 5448:vertices 5306:colors. 4587:, where 4334:for any 3814:Decision 3580:⌉ 3535:⌈ 3221:′ 3157:′ 3061:′ 2979:are not 2084:, where 1805:of size 1334:-bounded 754:– 2) … ( 680: : 676:) = min{ 657:,4) = 72 476:-partite 379:integers 348:coloring 112:embedded 67:vertices 8993:0051516 8981:0035428 8698:4760027 8575:2920058 8328:8857534 8165:Bibcode 7535:Bibcode 7457:1209067 7359:(Δ + 1) 6179:unless 6095:#P-hard 6014:NP-hard 5334:degrees 5065:colors. 4583:due to 4031: ( 3951:NP-hard 3861:colors? 2995:Theorem 2849:Theorem 2834:cliques 2230:, with 1646:, and 1064:⁠ 1035:⁠ 908:is the 298:Seymour 282:Shannon 140:History 8979: 8901: 8838: 8780: 8754: 8724: 8696: 8621: 8613: 8573: 8563: 8497: 8479: 8453: 8428: 8418: 8390: 8326: 8316: 8287: 8269: 8249: 8233: 8199: 8183: 8145: 8066: 8019: 8009: 7970: 7943: 7910: 7878: 7816:Eureka 7779: 7712: 7702: 7645: 7553: 7512: 7455: 7404: 7394: 6667: 6287:Sudoku 5920: 5822: 5796: 5759: 5704:reduce 5655:, and 5606:DSatur 5584:where 5456:vertex 5433:DSatur 5409:Brélaz 4939:1.6180 4743:where 4389:1.7272 4353:1.3289 4262:2.4423 4235:Using 4149:for a 4126:using 4110:using 4024:Output 4008:Graph 3935:Output 3922:Graph 3850:Output 3834:Graph 3626:, the 3614:has a 2916:whose 2871: 2863: 2855: 1803:clique 1512:degree 932:. The 863:– 352) 367:colors 302:Thomas 300:, and 125:Sudoku 8694:S2CID 8650:arXiv 8619:S2CID 8587:(PDF) 8515:(PDF) 8426:S2CID 8364:(PDF) 8324:S2CID 8181:S2CID 8143:S2CID 8064:S2CID 8046:arXiv 8017:S2CID 7908:S2CID 7876:S2CID 7831:(PDF) 7777:S2CID 7710:S2CID 7623:arXiv 7596:(PDF) 7573:(PDF) 7551:S2CID 7510:S2CID 7453:S2CID 7435:arXiv 7402:S2CID 7374:arXiv 6744:, in 6729:Notes 6595:stars 6242:is a 6149:FPRAS 6090:≥ 5. 5726:cycle 5682:In a 5653:cycle 5645:exact 5452:graph 5450:of a 5069:The 4418:The 4289:Yates 4077:FPRAS 4012:with 4005:Input 3926:with 3919:Input 3853:Does 3838:with 3831:Input 3624:minor 2999:Erdős 2988:girth 1650:have 1501:trees 1016:orbit 912:, or 887:edges 859:+ 775 855:– 814 851:+ 529 847:– 230 835:– 2)( 831:– 1)( 793:Cycle 771:with 762:– 1)) 750:– 1)( 721:– 1)( 642:– 1)( 532:every 83:of a 63:graph 8899:ISBN 8836:ISBN 8778:ISBN 8752:ISBN 8722:ISBN 8611:ISSN 8561:ISBN 8477:ISBN 8416:ISBN 8388:ISBN 8314:ISBN 8285:ISBN 8267:ISBN 8247:ISBN 8231:ISSN 8197:ISBN 8007:ISBN 7968:ISBN 7941:ISBN 7700:ISBN 7643:ISBN 7392:ISBN 7116:and 6679:and 5686:, a 5647:for 5466:The 5435:and 5317:and 5309:For 4966:for 4857:and 4849:and 4841:and 4833:and 4747:and 4633:and 4591:and 4474:i.e. 4460:and 4374:and 4287:and 4089:PTAS 3997:Name 3911:Name 3819:Name 3598:The 3395:are 2873:1955 2865:1949 2857:1947 2318:Let 1880:Let 1866:For 1685:and 1605:and 1137:. A 924:. A 843:+ 67 839:– 12 812:– 1) 786:– 1) 769:Tree 725:– 2) 646:– 2) 634:) = 525:The 478:and 375:blue 373:and 360:loop 356:edge 234:and 227:five 148:and 97:dual 8951:doi 8927:doi 8818:doi 8770:doi 8744:doi 8714:doi 8686:doi 8660:doi 8646:105 8603:doi 8553:doi 8527:doi 8461:doi 8408:doi 8349:doi 8306:doi 8223:doi 8173:doi 8161:108 8135:doi 8113:doi 8093:doi 8056:doi 8042:206 7999:doi 7931:doi 7898:doi 7866:doi 7843:doi 7839:107 7799:doi 7767:doi 7732:doi 7692:doi 7674:doi 7633:doi 7606:(= 7585:doi 7543:doi 7500:doi 7475:doi 7445:doi 7423:", 7384:doi 7132:; 6254:is 6012:is 5915:log 5876:log 5837:log 5817:log 5791:log 5768:log 5754:log 5736:to 5608:at 5563:log 5346:max 5274:on 5208:,…, 5100:,…, 5003:of 4514:min 4468:or 4114:or 4087:No 4054:O(2 3901:GT4 3869:O(2 3618:on 3411:of 3374:). 3315:or 3258:if 2193:max 2119:min 2097:max 2057:min 2036:max 1797:If 1377:in 1167:of 1010:An 964:χ″( 959:and 918:χ′( 881:An 758:– ( 617:in 536:any 371:red 288:by 253:by 190:at 108:map 49:In 9074:: 8990:MR 8977:MR 8973:24 8945:, 8921:, 8869:, 8814:10 8812:, 8776:, 8750:, 8720:, 8708:, 8692:, 8682:95 8680:, 8658:, 8617:, 8609:, 8595:14 8593:, 8589:, 8571:MR 8569:, 8559:, 8543:; 8521:, 8517:, 8459:, 8447:21 8445:, 8424:, 8414:, 8366:, 8343:, 8322:, 8312:, 8229:, 8219:88 8217:, 8213:, 8179:, 8171:, 8159:, 8141:, 8131:10 8129:, 8109:45 8107:, 8087:, 8081:, 8062:, 8054:, 8040:, 8030:; 8015:, 8005:, 7987:; 7983:; 7956:; 7939:, 7925:, 7906:, 7894:30 7892:, 7874:, 7862:11 7860:, 7837:, 7833:, 7820:21 7818:, 7795:30 7793:, 7775:, 7763:29 7761:, 7728:70 7726:, 7708:, 7698:, 7670:32 7668:, 7641:, 7631:, 7611:13 7581:54 7579:, 7575:, 7564:; 7549:, 7541:, 7531:37 7529:, 7508:, 7496:22 7494:, 7471:39 7469:, 7451:, 7443:, 7431:54 7429:, 7400:, 7390:, 7382:, 7189:^ 7099:; 7037:^ 7020:^ 6873:^ 6846:^ 6683:. 6238:A 6167:. 6165:RP 6161:NP 6016:. 5902:. 5773:, 5659:. 5651:, 5640:. 4865:. 4782:uv 4637:. 4626:uv 4487:: 4478:uv 4243:, 4130:. 3980:O( 3972:)) 3960:O( 3938:χ( 3642:. 3499:1. 3437:). 3426:≥ 3381:. 2983:. 2867:, 2859:, 2844:. 1874:. 1732:: 1555:1. 1514:, 1506:A 1492:. 978:. 916:, 672:χ( 659:. 580:… 577:72 574:12 560:… 423:χ( 415:γ( 407:χ( 296:, 292:, 53:, 8995:. 8953:: 8947:3 8929:: 8913:2 8865:G 8861:H 8820:: 8772:: 8746:: 8716:: 8688:: 8674:χ 8662:: 8652:: 8605:: 8578:. 8555:: 8536:. 8529:: 8523:3 8463:: 8410:: 8351:: 8345:5 8308:: 8225:: 8175:: 8167:: 8137:: 8115:: 8095:: 8089:1 8058:: 8048:: 8001:: 7933:: 7900:: 7868:: 7845:: 7801:: 7769:: 7734:: 7694:: 7676:: 7635:: 7625:: 7613:) 7587:: 7545:: 7537:: 7502:: 7477:: 7447:: 7437:: 7419:O 7386:: 7376:: 7363:Δ 7283:. 7271:. 7259:. 7247:. 7235:. 7223:. 7211:. 7199:. 7184:. 7172:. 7160:. 7148:. 7136:. 7120:. 7103:. 7087:. 7075:. 7047:. 7032:. 7015:. 7003:. 6991:. 6979:. 6967:. 6955:. 6943:. 6895:. 6868:. 6856:. 6841:. 6829:. 6817:. 6748:. 6622:T 6568:i 6564:i 6526:. 6520:k 6516:h 6482:. 6333:6 6329:K 6275:k 6271:k 6173:ε 6157:k 6153:k 6145:k 6141:k 6137:k 6120:) 6117:k 6114:, 6111:G 6108:( 6088:k 6073:1 6064:) 6055:2 6051:/ 6047:k 6040:k 6035:( 6021:k 6010:n 6006:ε 6002:n 5998:n 5979:k 5975:k 5963:k 5959:k 5955:k 5922:n 5917:* 5911:O 5887:) 5882:n 5871:( 5867:O 5863:2 5848:n 5844:n 5842:( 5839:* 5833:O 5824:n 5819:* 5815:( 5813:O 5806:n 5802:n 5798:n 5793:* 5783:n 5770:* 5761:n 5756:* 5752:( 5750:O 5746:n 5742:n 5738:O 5734:n 5724:- 5722:n 5715:n 5708:n 5700:n 5696:n 5628:) 5625:n 5622:m 5619:( 5616:O 5592:m 5572:) 5569:n 5560:) 5557:m 5554:+ 5551:n 5548:( 5545:( 5542:O 5522:n 5502:) 5497:2 5493:n 5489:( 5486:O 5395:} 5392:i 5389:, 5386:1 5383:+ 5380:) 5375:i 5371:x 5367:( 5364:d 5361:{ 5351:i 5294:2 5290:/ 5286:n 5276:n 5258:) 5255:G 5252:( 5227:1 5221:i 5217:v 5194:1 5190:v 5167:i 5163:v 5140:i 5136:v 5113:n 5109:v 5086:1 5082:v 5053:2 5049:/ 5045:n 5035:n 4991:) 4988:G 4985:( 4982:t 4972:m 4968:n 4954:) 4949:m 4946:+ 4943:n 4935:( 4932:O 4929:= 4924:m 4921:+ 4918:n 4913:) 4907:2 4901:5 4896:+ 4893:1 4886:( 4859:v 4855:u 4851:v 4847:u 4843:v 4839:u 4835:v 4831:u 4816:) 4813:k 4810:, 4807:v 4804:u 4798:G 4795:( 4792:P 4768:v 4765:u 4759:G 4749:v 4745:u 4728:) 4725:k 4722:, 4719:G 4716:( 4713:P 4710:+ 4707:) 4704:k 4701:, 4698:v 4695:u 4691:/ 4687:G 4684:( 4681:P 4678:= 4675:) 4672:k 4669:, 4666:v 4663:u 4657:G 4654:( 4651:P 4635:v 4631:u 4612:v 4609:u 4606:+ 4603:G 4593:v 4589:u 4568:} 4565:) 4562:v 4559:u 4555:/ 4551:G 4548:( 4542:, 4539:) 4536:v 4533:u 4530:+ 4527:G 4524:( 4518:{ 4510:= 4507:) 4504:G 4501:( 4470:v 4466:u 4462:v 4458:u 4454:G 4440:v 4437:u 4433:/ 4429:G 4398:) 4393:n 4385:( 4382:O 4362:) 4357:n 4349:( 4346:O 4336:k 4322:) 4319:n 4314:n 4310:2 4306:( 4303:O 4293:k 4271:) 4266:n 4258:( 4255:O 4245:k 4220:1 4214:n 4211:, 4205:, 4202:1 4199:= 4196:k 4186:n 4182:k 4166:n 4162:k 4151:k 4058:) 4056:n 4045:G 4041:k 4037:k 4035:, 4033:G 4029:P 4018:k 4014:n 4010:G 3982:n 3970:n 3966:n 3962:n 3942:) 3940:G 3928:n 3924:G 3873:) 3871:n 3859:k 3855:G 3844:k 3840:n 3836:G 3824:k 3777:0 3771:) 3768:4 3765:, 3762:G 3759:( 3756:P 3736:) 3730:, 3727:5 3724:[ 3704:) 3698:, 3695:4 3692:[ 3672:) 3669:t 3666:, 3663:G 3660:( 3657:P 3647:G 3636:k 3620:k 3612:k 3584:. 3575:2 3571:1 3568:+ 3565:) 3562:G 3559:( 3553:+ 3550:) 3547:G 3544:( 3528:) 3525:G 3522:( 3496:+ 3493:) 3490:G 3487:( 3478:) 3475:G 3472:( 3463:) 3460:G 3457:( 3431:0 3428:n 3424:n 3420:n 3415:. 3401:G 3397:k 3393:G 3370:( 3364:k 3352:k 3341:. 3329:1 3326:+ 3260:G 3246:) 3243:G 3240:( 3234:= 3231:) 3228:G 3225:( 3208:: 3185:. 3182:) 3179:G 3176:( 3167:) 3164:G 3161:( 3130:) 3127:G 3124:( 3098:. 3095:) 3092:) 3089:G 3086:( 3083:L 3080:( 3074:= 3071:) 3068:G 3065:( 3034:) 3031:G 3028:( 3025:L 3012:G 2997:( 2965:2 2960:R 2936:3 2931:R 2902:3 2897:R 2851:( 2812:. 2809:) 2806:G 2803:( 2794:) 2791:G 2788:( 2783:f 2772:) 2763:G 2757:( 2748:) 2745:G 2742:( 2737:V 2726:) 2723:G 2720:( 2715:H 2684:. 2681:) 2678:G 2675:( 2666:) 2663:G 2660:( 2655:f 2637:: 2618:. 2615:) 2612:G 2609:( 2600:) 2591:G 2585:( 2569:: 2550:. 2547:) 2544:G 2541:( 2532:) 2529:G 2526:( 2521:V 2493:W 2473:) 2470:G 2467:( 2462:V 2437:G 2417:) 2414:j 2411:, 2408:i 2405:( 2381:1 2375:k 2371:1 2357:j 2354:, 2351:i 2347:W 2326:W 2316:: 2295:. 2292:) 2289:G 2286:( 2277:) 2274:G 2271:( 2266:H 2238:W 2218:) 2215:G 2212:( 2207:W 2197:W 2189:= 2186:) 2183:G 2180:( 2175:H 2150:W 2130:) 2127:W 2124:( 2111:, 2108:) 2105:W 2102:( 2068:) 2065:W 2062:( 2047:) 2044:W 2041:( 2021:1 2018:= 2015:) 2012:G 2009:( 2004:W 1979:G 1959:) 1956:j 1953:, 1950:i 1947:( 1927:0 1924:= 1919:j 1916:, 1913:i 1909:W 1888:W 1851:. 1848:) 1845:G 1842:( 1833:) 1830:G 1827:( 1811:k 1807:k 1799:G 1783:G 1779:G 1765:) 1762:G 1759:( 1750:) 1747:G 1744:( 1708:2 1705:= 1702:) 1699:G 1696:( 1673:3 1670:= 1667:) 1664:G 1661:( 1634:1 1628:n 1625:= 1622:) 1619:G 1616:( 1593:n 1590:= 1587:) 1584:G 1581:( 1552:+ 1549:) 1546:G 1543:( 1534:) 1531:G 1528:( 1480:) 1477:G 1474:( 1468:= 1465:) 1462:) 1459:G 1456:( 1450:( 1447:c 1427:) 1424:) 1421:G 1418:( 1412:( 1409:c 1387:F 1365:G 1345:c 1298:F 1273:. 1270:m 1267:2 1261:) 1258:1 1252:) 1249:G 1246:( 1240:( 1237:) 1234:G 1231:( 1215:m 1201:n 1198:= 1195:) 1190:n 1186:K 1182:( 1169:n 1153:n 1149:K 1118:. 1115:n 1109:) 1106:G 1103:( 1094:1 1050:d 1045:Z 1031:d 976:G 972:G 968:) 966:G 922:) 920:G 906:G 899:k 895:k 891:k 861:t 857:t 853:t 849:t 845:t 841:t 837:t 833:t 829:t 827:( 825:t 810:t 806:t 804:( 798:n 796:C 784:t 782:( 780:t 773:n 760:n 756:t 752:t 748:t 746:( 744:t 737:n 735:K 723:t 719:t 717:( 715:t 708:3 705:K 690:k 688:, 686:G 684:( 682:P 678:k 674:G 668:χ 664:G 655:G 653:( 651:P 644:t 640:t 638:( 636:t 632:t 630:, 628:G 626:( 624:P 619:t 611:G 607:G 603:t 599:) 597:t 595:, 593:G 591:( 589:P 571:0 568:0 557:4 554:3 551:2 548:1 512:3 509:K 503:3 500:E 481:k 474:k 469:k 465:k 453:k 447:k 440:k 435:k 427:) 425:G 419:) 417:G 411:) 409:G 399:G 393:k 388:k 166:. 135:. 34:. 20:)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index