17:
211:
nor an odd cycle, and a list of Δ colors for each vertex, it is possible to choose a color for each vertex from its list so that no two adjacent vertices have the same color. In other words, the list chromatic number of a connected undirected graph G never exceeds Δ, unless G is a clique or an odd
286:
A Δ-coloring, or even a Δ-list-coloring, of a degree-Δ graph may be found in linear time. Efficient algorithms are also known for finding Brooks colorings in parallel and distributed models of computation.
470:
239:
For certain graphs, even fewer than Δ colors may be needed. Δ − 1 colors suffice if and only if the given graph has no Δ-clique,
542:
749:
143:, its small number of neighbors allows it to be colored. Therefore, the most difficult case of the proof concerns biconnected Δ-
648:
589:
443:
62:, who published a proof of it in 1941. A coloring with the number of colors described by Brooks' theorem is sometimes called a
673:
278:
states that any graph has a (Δ + 1)-coloring in which the sizes of any two color classes differ by at most one.
612:
Panconesi, Alessandro; Srinivasan, Aravind (1995), "The local nature of Δ-coloring and its algorithmic applications",
248:
179:
is colored, it has an uncolored parent, so its already-colored neighbors cannot use up all the free colors, while at
43:. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be
643:
119:, its biconnected components may be colored separately and then the colorings combined. If the graph has a vertex
23:
need one more color than their maximum degree. They and the odd cycles are the only exceptions to Brooks' theorem.
744:
507:
Grable, David A.; Panconesi, Alessandro (2000), "Fast distributed algorithms for Brooks–Vizing colourings",
139:) is uncolored, so it has fewer than Δ colored neighbors and has a free color. When the algorithm reaches
584:
232:
the same color as each other (if possible), or otherwise give one of them a color that is unavailable to
112:
208:
89:
36:
479:
212:
cycle. A small modification of the proof of Lovász applies to this case: for the same three vertices
434:
263:
244:
131:
before closer ones uses at most Δ colors. This is because at the time that each vertex other than
631:
524:
495:
275:
104:
is a complete graph or an odd cycle, in which case the chromatic number is Δ + 1.
537:
717:
465:
270:, stating that the total chromatic number is at most Δ + 2, has been conjectured by
116:
59:
682:
657:
623:
598:
572:
551:
516:
487:
452:
93:
82:
40:
124:
79:
171:
and processing the remaining vertices of the spanning tree in bottom-up order, ending at
483:
267:
48:
44:
20:
738:
614:
603:
576:
499:
438:
259:
204:
148:
144:
635:
528:
258:
The degree of a graph also appears in upper bounds for other types of coloring; for
16:
721:
271:
252:
28:
52:
207:: given any connected undirected graph with maximum degree Δ that is neither a
686:
491:
726:
430:
147:
graphs with Δ ≥ 3. In this case, Lovász shows that one can find a
662:
520:
457:
671:
Skulrattanakulchai, San (2006), "Δ-List vertex coloring in linear time",
135:
is colored, at least one of its neighbors (the one on a shortest path to
627:
555:
262:, the result that the chromatic index is at most Δ + 1 is
115:
gives a simplified proof of Brooks' theorem. If the graph is not
471:
Mathematical
Proceedings of the Cambridge Philosophical Society
563:
Karloff, H. J. (1989), "An NC algorithm for Brooks' theorem",
694:
Vizing, V. G. (1976), "Vertex colorings with given colors",
175:, uses at most Δ colors. For, when every vertex other than
163:
are leaves in the tree. A greedy coloring starting from
377:
441:(1999), "Coloring graphs with sparse neighborhoods",
236:, and then complete the coloring greedily as before.
55:
of odd length, which require Δ + 1 colors.
301:
299:
191:
have equal colors so again a free color remains for
409:
329:
389:
203:A more general version of the theorem applies to
468:(1941), "On colouring the nodes of a network",
413:
405:
317:
646:(1999), "A strengthening of Brooks' theorem",
587:(1975), "Three short proofs in graph theory",
8:
274:and Vizing. The Hajnal–Szemerédi theorem on
127:algorithm that colors vertices farther from
47:with only Δ colors, except for two cases,
35:states a relationship between the maximum
661:
602:
456:
247:, or more generally graphs in which the
15:
540:(1990), "Brooks coloring in parallel",
401:
295:
378:Alon, Krivelevich & Sudakov (1999)
353:
341:
305:
266:. An extension of Brooks' theorem to
7:
543:SIAM Journal on Discrete Mathematics
365:
151:such that two nonadjacent neighbors
255:, O(Δ/log Δ) colors suffice.
14:
410:Panconesi & Srinivasan (1995)
330:Panconesi & Srinivasan (1995)
251:of every vertex is sufficiently
123:with degree less than Δ, then a
649:Journal of Combinatorial Theory
590:Journal of Combinatorial Theory
444:Journal of Combinatorial Theory
674:Information Processing Letters
1:
414:Grable & Panconesi (2000)
406:Hajnal & Szemerédi (1990)
318:Hajnal & Szemerédi (1990)
224:from that proof, either give
604:10.1016/0095-8956(75)90089-1
577:10.1016/0304-3975(89)90121-7
565:Theoretical Computer Science
58:The theorem is named after
766:
687:10.1016/j.ipl.2005.12.007
492:10.1017/S030500410002168X
390:Skulrattanakulchai (2006)
750:Theorems in graph theory
243:Δ is large enough. For
663:10.1006/jctb.1998.1891
521:10.1006/jagm.2000.1097
458:10.1006/jctb.1999.1910
24:
509:Journal of Algorithms
100:is at most Δ, unless
19:
435:Krivelevich, Michael
245:triangle-free graphs
484:1941PCPS...37..194B
39:of a graph and its
718:Weisstein, Eric W.
628:10.1007/BF01200759
276:equitable coloring
183:the two neighbors
25:
722:"Brooks' Theorem"
60:R. Leonard Brooks
757:
731:
730:
703:
696:Diskret. Analiz.
689:
666:
665:
638:
607:
606:
579:
558:
538:Szemerédi, Endre
531:
502:
461:
460:
417:
399:
393:
387:
381:
375:
369:
363:
357:
351:
345:
339:
333:
327:
321:
315:
309:
303:
264:Vizing's theorem
94:chromatic number
83:undirected graph
74:Formal statement
41:chromatic number
765:
764:
760:
759:
758:
756:
755:
754:
735:
734:
716:
715:
712:
707:
693:
670:
642:
611:
583:
562:
556:10.1137/0403008
536:Hajnal, PĂ©ter;
535:
506:
464:
429:
425:
420:
400:
396:
388:
384:
376:
372:
364:
360:
352:
348:
340:
336:
328:
324:
316:
312:
304:
297:
293:
284:
201:
125:greedy coloring
110:
76:
64:Brooks coloring
49:complete graphs
33:Brooks' theorem
21:Complete graphs
12:
11:
5:
763:
761:
753:
752:
747:
745:Graph coloring
737:
736:
733:
732:
711:
710:External links
708:
706:
705:
698:(in Russian),
691:
681:(3): 101–106,
668:
656:(2): 136–149,
640:
622:(2): 255–280,
609:
597:(3): 269–271,
581:
560:
533:
504:
478:(2): 194–197,
462:
439:Sudakov, Benny
426:
424:
421:
419:
418:
402:Karloff (1989)
394:
382:
370:
358:
346:
334:
322:
310:
294:
292:
289:
283:
280:
268:total coloring
200:
197:
109:
106:
75:
72:
13:
10:
9:
6:
4:
3:
2:
762:
751:
748:
746:
743:
742:
740:
729:
728:
723:
719:
714:
713:
709:
701:
697:
692:
688:
684:
680:
676:
675:
669:
664:
659:
655:
651:
650:
645:
641:
637:
633:
629:
625:
621:
617:
616:
615:Combinatorica
610:
605:
600:
596:
592:
591:
586:
582:
578:
574:
571:(1): 89–103,
570:
566:
561:
557:
553:
549:
545:
544:
539:
534:
530:
526:
522:
518:
514:
510:
505:
501:
497:
493:
489:
485:
481:
477:
473:
472:
467:
466:Brooks, R. L.
463:
459:
454:
450:
446:
445:
440:
436:
432:
428:
427:
422:
415:
411:
407:
403:
398:
395:
391:
386:
383:
379:
374:
371:
367:
362:
359:
355:
354:Vizing (1976)
350:
347:
343:
342:Lovász (1975)
338:
335:
331:
326:
323:
319:
314:
311:
307:
306:Brooks (1941)
302:
300:
296:
290:
288:
281:
279:
277:
273:
269:
265:
261:
260:edge coloring
256:
254:
250:
246:
242:
237:
235:
231:
227:
223:
219:
215:
210:
206:
205:list coloring
198:
196:
194:
190:
186:
182:
178:
174:
170:
166:
162:
158:
154:
150:
149:spanning tree
146:
142:
138:
134:
130:
126:
122:
118:
114:
113:László Lovász
107:
105:
103:
99:
95:
91:
88:with maximum
87:
84:
81:
73:
71:
69:
65:
61:
56:
54:
50:
46:
42:
38:
34:
30:
22:
18:
725:
699:
695:
678:
672:
653:
652:, Series B,
647:
619:
613:
594:
593:, Series B,
588:
568:
564:
550:(1): 74–80,
547:
541:
512:
508:
475:
469:
451:(1): 73–82,
448:
447:, Series B,
442:
397:
385:
373:
361:
349:
337:
325:
313:
285:
272:Mehdi Behzad
257:
249:neighborhood
240:
238:
233:
229:
225:
221:
217:
213:
202:
192:
188:
184:
180:
176:
172:
168:
164:
160:
159:of the root
156:
152:
140:
136:
132:
128:
120:
111:
101:
97:
85:
77:
67:
63:
57:
53:cycle graphs
32:
29:graph theory
26:
644:Reed, Bruce
366:Reed (1999)
117:biconnected
739:Categories
585:Lovász, L.
515:: 85–120,
431:Alon, Noga
423:References
282:Algorithms
199:Extensions
727:MathWorld
500:209835194
80:connected
636:28307157
529:14211416
241:provided
195:itself.
78:For any
68:coloring
480:Bibcode
145:regular
92:Δ, the
66:or a Δ-
45:colored
702:: 3–10
634:
527:
498:
253:sparse
220:, and
209:clique
90:degree
37:degree
632:S2CID
525:S2CID
496:S2CID
291:Notes
108:Proof
228:and
187:and
167:and
155:and
51:and
683:doi
658:doi
624:doi
599:doi
573:doi
552:doi
517:doi
488:doi
453:doi
96:of
27:In
741::
724:,
720:,
700:29
679:98
677:,
654:76
630:,
620:15
618:,
595:19
569:68
567:,
546:,
523:,
513:37
511:,
494:,
486:,
476:37
474:,
449:77
437:;
433:;
412:;
408:;
404:;
298:^
216:,
70:.
31:,
704:.
690:.
685::
667:.
660::
639:.
626::
608:.
601::
580:.
575::
559:.
554::
548:3
532:.
519::
503:.
490::
482::
455::
416:.
392:.
380:.
368:.
356:.
344:.
332:.
320:.
308:.
234:v
230:w
226:u
222:w
218:v
214:u
193:v
189:w
185:u
181:v
177:v
173:v
169:w
165:u
161:v
157:w
153:u
141:v
137:v
133:v
129:v
121:v
102:G
98:G
86:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
