20:
264:. They proved that every triangle-free planar graph can be represented by a collection of line segments, with three slopes, such that two vertices of the graph are adjacent if and only if the line segments representing them cross. A 3-coloring of the graph may then be obtained by assigning two vertices the same color whenever their line segments have the same slope.
54:, every graph that can be drawn in the plane without edge crossings can have its vertices colored using at most four different colors, so that the two endpoints of every edge have different colors, but according to Grötzsch's theorem only three colors are needed for planar graphs that do not contain three mutually adjacent vertices.
92:. However, Grötzsch's theorem itself does not extend from coloring to list coloring: there exist triangle-free planar graphs that are not 3-list-colorable. In 2012, Nabiha Asghar gave a new and much simpler proof of the theorem that is inspired by Thomassen's work.
211:, a 4-chromatic graph. By combining these two results, it may be shown that every triangle-free planar graph has a homomorphism to a triangle-free 3-colorable graph, the
468:
511:
240:
are both non-planar; there does not exist a triangle-free planar graph to which every other triangle-free planar graph may be mapped by a homomorphism.
144:
The theorem cannot be generalized to all nonplanar triangle-free graphs: not every nonplanar triangle-free graph is 3-colorable. In particular, the
77:
version of the theorem: a 3-edge-connected planar graph (or more generally a planar graph with no bridges and at most three 3-edge cuts) has a
551:
783:
857:
813:
156:
is a transformation of graphs that can be used to construct triangle-free graphs that require arbitrarily high numbers of colors.
100:
A slightly more general result is true: if a planar graph has at most three triangles then it is 3-colorable. However, the planar
729:
595:
Glebov, A. N.; Kostochka, A. V.; Tashkinov, V. A. (2005), "Smaller planar triangle-free graphs that are not 3-list-colorable",
138:
672:
200:. In the language of homomorphisms, Grötzsch's theorem states that every triangle-free planar graph has a homomorphism to
547:
358:
122:
253:
503:
763:
212:
394:
84:
In 2003, Carsten
Thomassen derived an alternative proof from another related theorem: every planar graph with
618:(1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel",
847:
759:
852:
543:
539:
354:
118:
125:
announced a proof of another generalization, conjectured in 1969 by L. Havel: there exists a constant
570:
376:
223:
85:
615:
578:
63:
40:
716:
560:
366:
257:
186:
51:
638:
363:
Three-coloring triangle-free graphs on surfaces V. Coloring planar graphs with distant anomalies
779:
145:
78:
825:
771:
738:
708:
693:
650:
604:
520:
149:
793:
752:
664:
631:
532:
800:
Steinberg, Richard; Younger, D. H. (1989), "Grötzsch's
Theorem for the projective plane",
789:
748:
660:
627:
528:
574:
380:
173:. In particular, there exists a planar graph without 4-cycles that cannot be 3-colored.
207:. Naserasr showed that every triangle-free planar graph also has a homomorphism to the
134:
101:
47:
830:
841:
208:
89:
770:, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, pp. 15–16,
720:
482:
261:
43:
32:
19:
678:
273:
153:
74:
28:
743:
608:
775:
712:
272:
Given a triangle-free planar graph, a 3-coloring of the graph can be found in
166:-free graphs, either: not every planar graph that requires 4 colors contains
727:
Naserasr, Reza (2007), "Homomorphisms and edge-colourings of planar graphs",
655:
222:
with the
Clebsch graph. The coloring of the graph may then be recovered by
66:, who published its proof in 1959. Grötzsch's original proof was complex.
226:
this homomorphism with the homomorphism from this tensor product to its
137:
with three colors. This work formed part of the basis for Dvořák's 2015
524:
550:(2009), "Three-coloring triangle-free planar graphs in linear time",
73:
In 1989, Richard
Steinberg and Dan Younger formulated and proved a
565:
371:
129:
such that, if a planar graph has no two triangles within distance
18:
233:
factor. However, the
Clebsch graph and its tensor product with
502:
de Castro, N.; Cobos, F. J.; Dana, J. C.; Márquez, A. (2002),
620:
Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe
485:(1960), "Les problèmes de colaration en théorie des graphs",
504:"Triangle-free planar graphs as segment intersection graphs"
117:, contain four triangles and are not 3-colorable. In 2009,
816:(2003), "A short list color proof of Grötzsch's theorem",
446:
249:
434:
330:
152:
are triangle-free graphs requiring four colors, and the
449:. For earlier work on algorithms for this problem, see
110:, and infinitely many other planar graphs containing
70:
attempted to simplify it but his proof was erroneous.
553:
Proc. 20th ACM-SIAM Symposium on
Discrete Algorithms
307:
159:The theorem cannot be generalized to all planar
62:The theorem is named after German mathematician
16:Every triangle-free planar graph is 3-colorable
694:"Fast 3-coloring triangle-free planar graphs"
641:(1963), "Grötzsch's theorem on 3-colorings",
8:
512:Journal of Graph Algorithms and Applications
23:A 3-coloring of a triangle-free planar graph
256:on the representation of planar graphs as
829:
818:Journal of Combinatorial Theory, Series B
742:
654:
564:
447:Dvořák, Kawarabayashi & Thomas (2009)
370:
319:
50:with only three colors. According to the
496:
430:
331:Glebov, Kostochka & Tashkinov (2005)
295:
476:Master's Thesis, University of Waterloo
450:
418:
285:
766:(2012), "2.5 Homomorphism Dualities",
435:Nešetřil & Ossona de Mendez (2012)
401:, University of Bergen, September 2015
342:
395:"The European Prize in Combinatorics"
291:
289:
67:
7:
674:Progress on Steinberg's Conjecture
671:Heckman, Christopher Carl (2007),
14:
252:combines Grötzsch's theorem with
487:Publ. Inst. Statist. Univ. Paris
177:Factoring through a homomorphism
730:Journal of Combinatorial Theory
139:European Prize in Combinatorics
308:Steinberg & Younger (1989)
133:of each other, then it can be
1:
831:10.1016/S0095-8956(03)00029-7
39:is the statement that every
874:
744:10.1016/j.jctb.2006.07.001
609:10.1016/j.disc.2004.10.015
776:10.1007/978-3-642-27875-4
764:Ossona de Mendez, Patrice
713:10.1007/s00453-009-9295-2
858:Theorems in graph theory
692:Kowalik, Łukasz (2010),
268:Computational complexity
254:Scheinerman's conjecture
244:Geometric representation
181:A 3-coloring of a graph
96:Larger classes of graphs
544:Kawarabayashi, Ken-ichi
467:Asghar, Nabiha (2012),
250:de Castro et al. (2002)
656:10.1307/mmj/1028998916
559:, pp. 1176–1182,
185:may be described by a
24:
22:
597:Discrete Mathematics
469:"Grötzsch's Theorem"
575:2013arXiv1302.5121D
381:2009arXiv0911.0885D
258:intersection graphs
79:nowhere-zero 3-flow
814:Thomassen, Carsten
760:Nešetřil, Jaroslav
525:10.7155/jgaa.00043
187:graph homomorphism
52:four-color theorem
37:Grötzsch's theorem
25:
785:978-3-642-27874-7
643:Michigan Math. J.
616:Grötzsch, Herbert
88:at least five is
865:
834:
833:
809:
802:Ars Combinatoria
796:
755:
746:
723:
698:
688:
687:
686:
677:, archived from
667:
658:
639:Grünbaum, Branko
634:
611:
603:(2–3): 269–274,
591:
590:
589:
583:
577:, archived from
568:
558:
535:
508:
494:
478:
473:
454:
444:
438:
428:
422:
416:
410:
408:
407:
406:
391:
385:
383:
374:
357:; Kráľ, Daniel;
351:
345:
340:
334:
328:
322:
320:Thomassen (2003)
317:
311:
305:
299:
293:
90:3-list-colorable
64:Herbert Grötzsch
873:
872:
868:
867:
866:
864:
863:
862:
838:
837:
812:
799:
786:
758:
726:
696:
691:
684:
682:
670:
637:
614:
594:
587:
585:
581:
556:
538:
506:
501:
497:Grünbaum (1963)
481:
471:
466:
463:
458:
457:
445:
441:
431:Naserasr (2007)
429:
425:
417:
413:
404:
402:
393:
392:
388:
353:
352:
348:
341:
337:
329:
325:
318:
314:
306:
302:
296:Grünbaum (1963)
294:
287:
282:
270:
246:
239:
232:
221:
206:
199:
179:
172:
165:
116:
109:
98:
60:
17:
12:
11:
5:
871:
869:
861:
860:
855:
850:
848:Graph coloring
840:
839:
836:
835:
824:(1): 189–192,
810:
797:
784:
756:
737:(3): 394–400,
724:
707:(3): 770–789,
689:
668:
649:(3): 303–310,
635:
612:
592:
540:Dvořák, Zdeněk
536:
499:
495:, as cited by
479:
462:
459:
456:
455:
451:Kowalik (2010)
439:
433:, Theorem 11;
423:
419:Heckman (2007)
411:
386:
355:Dvořák, Zdeněk
346:
335:
323:
312:
300:
284:
283:
281:
278:
269:
266:
245:
242:
237:
230:
219:
213:tensor product
204:
197:
193:to a triangle
178:
175:
170:
163:
146:Grötzsch graph
114:
107:
102:complete graph
97:
94:
59:
56:
15:
13:
10:
9:
6:
4:
3:
2:
870:
859:
856:
854:
853:Planar graphs
851:
849:
846:
845:
843:
832:
827:
823:
819:
815:
811:
807:
803:
798:
795:
791:
787:
781:
777:
773:
769:
765:
761:
757:
754:
750:
745:
740:
736:
732:
731:
725:
722:
718:
714:
710:
706:
702:
695:
690:
681:on 2012-07-22
680:
676:
675:
669:
666:
662:
657:
652:
648:
644:
640:
636:
633:
629:
625:
621:
617:
613:
610:
606:
602:
598:
593:
584:on 2012-10-18
580:
576:
572:
567:
562:
555:
554:
549:
548:Thomas, Robin
545:
541:
537:
534:
530:
526:
522:
518:
514:
513:
505:
500:
498:
492:
488:
484:
483:Berge, Claude
480:
477:
470:
465:
464:
460:
452:
448:
443:
440:
436:
432:
427:
424:
420:
415:
412:
400:
399:EuroComb 2015
396:
390:
387:
382:
378:
373:
368:
364:
360:
359:Thomas, Robin
356:
350:
347:
344:
343:Asghar (2012)
339:
336:
332:
327:
324:
321:
316:
313:
309:
304:
301:
297:
292:
290:
286:
279:
277:
275:
267:
265:
263:
262:line segments
259:
255:
251:
243:
241:
236:
229:
225:
218:
214:
210:
209:Clebsch graph
203:
196:
192:
188:
184:
176:
174:
169:
162:
157:
155:
151:
150:Chvátal graph
147:
142:
140:
136:
132:
128:
124:
120:
113:
106:
103:
95:
93:
91:
87:
82:
80:
76:
71:
69:
65:
57:
55:
53:
49:
45:
42:
41:triangle-free
38:
34:
30:
21:
821:
817:
805:
801:
767:
734:
733:, Series B,
728:
704:
701:Algorithmica
700:
683:, retrieved
679:the original
673:
646:
642:
623:
619:
600:
596:
586:, retrieved
579:the original
552:
516:
510:
490:
486:
475:
442:
426:
414:
403:, retrieved
398:
389:
362:
349:
338:
326:
315:
303:
271:
248:A result of
247:
234:
227:
216:
201:
194:
190:
182:
180:
167:
160:
158:
143:
130:
126:
121:, Kráľ, and
111:
104:
99:
83:
72:
68:Berge (1960)
61:
44:planar graph
36:
33:graph theory
29:mathematical
26:
626:: 109–120,
519:(1): 7–26,
274:linear time
154:Mycielskian
75:planar dual
842:Categories
685:2012-07-27
588:2013-02-22
461:References
405:2015-09-16
566:1302.5121
493:: 123–160
372:0911.0885
224:composing
31:field of
768:Sparsity
361:(2009),
148:and the
808:: 15–31
794:2920058
753:2305893
721:7152581
665:0154274
632:0116320
571:Bibcode
533:1898201
377:Bibcode
135:colored
58:History
48:colored
46:can be
27:In the
792:
782:
751:
719:
663:
630:
531:
123:Thomas
119:Dvořák
717:S2CID
697:(PDF)
582:(PDF)
561:arXiv
557:(PDF)
507:(PDF)
472:(PDF)
367:arXiv
280:Notes
189:from
86:girth
780:ISBN
826:doi
772:doi
739:doi
709:doi
651:doi
605:doi
601:290
521:doi
260:of
215:of
844::
822:88
820:,
806:28
804:,
790:MR
788:,
778:,
762:;
749:MR
747:,
735:97
715:,
705:58
703:,
699:,
661:MR
659:,
647:10
645:,
628:MR
622:,
599:,
569:,
546:;
542:;
529:MR
527:,
515:,
509:,
489:,
474:,
397:,
375:,
365:,
288:^
276:.
141:.
81:.
35:,
828::
774::
741::
711::
653::
624:8
607::
573::
563::
523::
517:6
491:9
453:.
437:.
421:.
409:.
384:.
379::
369::
333:.
310:.
298:.
238:3
235:K
231:3
228:K
220:3
217:K
205:3
202:K
198:3
195:K
191:G
183:G
171:4
168:K
164:4
161:K
131:d
127:d
115:4
112:K
108:4
105:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
