56:
575:, a conclusion considered unlikely by complexity theorists. However, it is not known how to prove non-polynomial lower bounds on the Hajós number without making some complexity-theoretic assumption, and if such a bound could be proven it would also imply the existence of non-polynomial bounds on certain types of
68:
by identifying a vertex from each copy into a single vertex (shown with both colors), deleting an edge incident to the combined vertex within each subgraph (dashed) and adding a new edge connecting the endpoints of the deleted edges (thick green), produces the
327:, and the effect of identifying two nonadjacent vertices is to force them to have the same color as each other in any coloring, something that does not reduce the number of colors. In the Hajós construction itself, the new edge
544:, where each step forms a new graph by combining two previously formed graphs, merging two nonadjacent vertices of a previously formed graph, or adding a vertex or edge to a previously formed graph. They showed that, for an
386:
colors may be formed by combining the Hajós construction, the operation of identifying any two nonadjacent vertices, and the operations of adding a vertex or edge to the given graph, starting from the complete graph
148:
on four vertices; because of the symmetry of these graphs, the choice of which edge to select from each of them is unimportant. In this case, the result of applying the Hajós construction is the
602:
may re-use the same graphs multiple times, an economy not permitted in an expression tree. There exist 3-chromatic graphs for which the smallest such expression tree has exponential size.
347:, so any proper coloring of the combined graph leads to a proper coloring of one of the two smaller graphs from which it was formed, which again causes it to require
496:
Because merging two non-adjacent vertices reduces the number of vertices in the resulting graph, the number of operations needed to represent a given graph
745:, 11.6 Length of Hajós proofs, pp. 184–185, state as an open problem the question of determining the smallest number of steps needed to construct every
1083:
1056:
1002:
852:
825:
1115:
440:
977:
928:
791:
1014:
872:
649:
567:. If every graph has a polynomial Hajós number, this would imply that it is possible to prove non-colorability in
1163:
637:
1066:
Liu, Sheng; Zhang, Jian (2006), "Using Hajós' construction to generate hard graph 3-colorability instances",
1168:
1124:
105:. Then the Hajós construction forms a new graph that combines the two graphs by identifying vertices
179:
respectively, then the result of applying the Hajós construction is itself a cycle graph, of length
1129:
645:
626:
153:
820:, Graduate Texts in Mathematics, vol. 173 (3rd ed.), Springer-Verlag, pp. 117–118,
580:
903:
32:
1079:
1052:
1046:
998:
848:
839:, Lecture Notes in Computer Science, vol. 2570, Berlin: Springer-Verlag, pp. 39–47,
821:
622:
815:
1134:
1071:
1023:
973:
944:
881:
840:
800:
789:
Catlin, P. A. (1979), "Hajós's graph-colouring conjecture: variations and counterexamples",
614:
296:
86:
44:
28:
1146:
1102:
1037:
985:
956:
895:
862:
1142:
1110:
1098:
1093:
Mansfield, A. J.; Welsh, D. J. A. (1982), "Some colouring problems and their complexity",
1033:
981:
952:
932:
891:
858:
587:
568:
485:
1070:, Lecture Notes in Computer Science, vol. 4120, Springer-Verlag, pp. 211–225,
1097:, North-Holland Math. Stud., vol. 62, Amsterdam: North-Holland, pp. 159–170,
1051:, Contemporary Mathematics, vol. 352, American Mathematical Society, p. 156,
371:
359:
317:
137:
40:
741:
alludes to this when he writes that the sequence of operations is "not always short".
1157:
1028:
964:
Jensen, Tommy R.; Royle, Gordon F. (1999), "Hajós constructions of critical graphs",
948:
886:
805:
424:-constructible graph such that all of the graphs formed in its construction are also
398:
149:
70:
630:
576:
481:
244:-constructible graphs. Then the graph formed by applying the Hajós construction to
20:
55:
168:
1012:
Koester, Gerhard (1991), "On 4-critical planar graphs with high edge density",
1138:
844:
500:
using the operations defined by Hajós may exceed the number of vertices in
652:
1075:
978:
10.1002/(SICI)1097-0118(199901)30:1<37::AID-JGT5>3.0.CO;2-V
613:
used the Hajós construction to generate an infinite set of 4-critical
291:-constructible. Equivalently, this graph may be formed by adding edge
1113:; Urquhart, Alasdair (1995), "The complexity of the Hajós calculus",
935:(1995), "Exponential lower bounds for the tree-like Hajós calculus",
378:
colors but for which every proper subgraph requires fewer colors) is
617:, each having more than twice as many edges as vertices. Similarly,
870:
Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring",
214:-constructible) when it formed in one of the following three ways:
572:
454:, also serves as a counterexample to this problem. Subsequently,
420:-critical graph (that is, every odd cycle) can be generated as a
912:
Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe
629:, which they showed to be difficult to color using traditional
835:
Euler, Reinhardt (2003), "Hajós' construction and polytopes",
354:
Hajós proved more strongly that a graph requires at least
382:-constructible. Alternatively, every graph that requires
366:-constructible graph as a subgraph. Equivalently, every
339:
to have a different color than the combined vertex for
533:
to be the minimum number of steps needed to construct
594:
may be significantly larger than the Hajós number of
590:describing a Hajós construction for a given graph
480:, one such example is the graph obtained from the
59:Applying the Hajós construction to two copies of
1068:Artificial Intelligence and Symbolic Computation
484:graph by adding a new edge between each pair of
761:
320:. Indeed, this is clear for the complete graph
837:Combinatorial optimization—Eureka, you shrink!
508:
113:into a single vertex, removing the two edges
8:
773:
726:
447:-chromatic graphs contain a subdivision of
308:It is straightforward to verify that every
921:
742:
698:
571:, and therefore imply that NP =
1128:
1027:
885:
804:
621:used the construction, starting with the
644:used the Hajós construction to generate
618:
331:forces at least one of the two vertices
54:
993:Jensen, Tommy R.; Toft, Bjarne (1994),
738:
710:
686:
673:
663:
610:
397:A similar construction may be used for
312:-constructible graph requires at least
906:(1961), "Über eine Konstruktion nicht
757:
755:
714:
436:
997:(2nd ed.), John Wiley and Sons,
669:
667:
641:
462:-constructible graphs solely through
435:, this is not true: a graph found by
279:. Then the graph formed by combining
36:
7:
1116:SIAM Journal on Discrete Mathematics
598:, because a shortest expression for
466:-critical graphs were found for all
275:be any two non-adjacent vertices in
39:) that may be used to construct any
405:Constructibility of critical graphs
47:is at least some given threshold.
14:
569:nondeterministic polynomial time
792:Journal of Combinatorial Theory
362:, if and only if it contains a
23:, a branch of mathematics, the
1095:Graph theory (Cambridge, 1981)
937:Information Processing Letters
625:, to generate many 4-critical
267:-constructible graph, and let
1:
762:Pitassi & Urquhart (1995)
685:A proof can also be found in
287:into a single vertex is also
1029:10.1016/0012-365X(91)90039-5
949:10.1016/0020-0190(95)00035-B
887:10.1016/0012-365X(95)00350-6
806:10.1016/0095-8956(79)90062-5
509:Mansfield & Welsh (1982)
156:that requires four colors.
1185:
814:Diestel, Reinhard (2006),
774:Iwama & Pitassi (1995)
1139:10.1137/S089548019224024X
727:Jensen & Royle (1999)
922:Jensen & Toft (1994)
743:Jensen & Toft (1994)
699:Jensen & Toft (1994)
638:polyhedral combinatorics
121:, and adding a new edge
995:Graph Coloring Problems
966:Journal of Graph Theory
845:10.1007/3-540-36478-1_6
586:The minimum size of an
439:as a counterexample to
374:(a graph that requires
159:As another example, if
1045:Kubale, Marek (2004),
619:Liu & Zhang (2006)
401:in place of coloring.
304:Connection to coloring
295:to the graph and then
74:
910:-färbbarer Graphen",
318:proper graph coloring
58:
1015:Discrete Mathematics
873:Discrete Mathematics
627:triangle-free graphs
194:Constructible graphs
1076:10.1007/11856290_19
507:More specifically,
218:The complete graph
154:unit distance graph
43:or any graph whose
29:operation on graphs
606:Other applications
581:mathematical logic
458:-critical but not
441:Hajós's conjecture
75:
25:Hajós construction
1085:978-3-540-39728-1
1058:978-0-8218-3458-9
1004:978-0-471-02865-9
854:978-3-540-00580-3
827:978-3-540-26183-4
615:polyhedral graphs
529:-chromatic graph
152:, a seven-vertex
128:For example, let
87:undirected graphs
1176:
1164:Graph operations
1149:
1132:
1111:Pitassi, Toniann
1105:
1088:
1061:
1040:
1031:
1007:
988:
959:
933:Pitassi, Toniann
919:
909:
898:
889:
880:(1–3): 299–302,
865:
830:
809:
808:
777:
771:
765:
759:
750:
748:
736:
730:
724:
718:
708:
702:
696:
690:
683:
677:
671:
601:
597:
593:
566:
555:
551:
547:
543:
536:
532:
528:
524:
503:
499:
492:The Hajós number
479:
472:
465:
461:
457:
453:
446:
434:
427:
423:
419:
415:
393:
385:
381:
377:
369:
365:
357:
350:
346:
342:
338:
334:
330:
326:
315:
311:
294:
290:
286:
282:
278:
274:
270:
266:
262:
255:
251:
247:
243:
239:
235:
228:
224:
213:
205:
201:
189:
178:
174:
166:
162:
147:
135:
131:
124:
120:
116:
112:
108:
104:
100:
96:
92:
84:
80:
67:
51:The construction
45:chromatic number
33:György Hajós
1184:
1183:
1179:
1178:
1177:
1175:
1174:
1173:
1154:
1153:
1109:
1092:
1086:
1065:
1059:
1048:Graph Colorings
1044:
1011:
1005:
992:
963:
927:
907:
902:
869:
855:
834:
828:
813:
788:
785:
780:
772:
768:
760:
753:
746:
737:
733:
725:
721:
709:
705:
697:
693:
684:
680:
672:
665:
661:
608:
599:
595:
591:
588:expression tree
565:) ≤ 2 − 1
557:
553:
549:
545:
542:
538:
534:
530:
526:
515:
501:
497:
494:
474:
467:
463:
459:
455:
452:
448:
444:
429:
428:-critical. For
425:
421:
417:
410:
407:
392:
388:
383:
379:
375:
367:
363:
360:proper coloring
358:colors, in any
355:
348:
344:
340:
336:
332:
328:
325:
321:
313:
309:
306:
292:
288:
284:
280:
276:
272:
268:
264:
260:
256:-constructible.
253:
249:
245:
241:
237:
233:
229:-constructible.
226:
223:
219:
211:
203:
199:
196:
180:
176:
172:
164:
160:
146:
140:
133:
129:
122:
118:
114:
110:
106:
102:
98:
94:
90:
82:
78:
66:
60:
53:
17:
16:Graph operation
12:
11:
5:
1182:
1180:
1172:
1171:
1169:Graph coloring
1166:
1156:
1155:
1152:
1151:
1130:10.1.1.30.5879
1123:(3): 464–483,
1107:
1090:
1084:
1063:
1057:
1042:
1022:(2): 147–151,
1009:
1003:
990:
961:
943:(5): 289–294,
925:
920:. As cited by
900:
867:
853:
832:
826:
811:
799:(2): 268–274,
784:
781:
779:
778:
766:
751:
749:-vertex graph.
739:Diestel (2006)
731:
719:
711:Gravier (1996)
703:
691:
687:Diestel (2006)
678:
674:Diestel (2006)
662:
660:
657:
623:Grötzsch graph
611:Koester (1991)
607:
604:
548:-vertex graph
540:
493:
490:
450:
406:
403:
390:
372:critical graph
323:
316:colors in any
305:
302:
301:
300:
257:
230:
221:
202:is said to be
195:
192:
144:
138:complete graph
101:be an edge of
93:be an edge of
64:
52:
49:
41:critical graph
15:
13:
10:
9:
6:
4:
3:
2:
1181:
1170:
1167:
1165:
1162:
1161:
1159:
1148:
1144:
1140:
1136:
1131:
1126:
1122:
1118:
1117:
1112:
1108:
1104:
1100:
1096:
1091:
1087:
1081:
1077:
1073:
1069:
1064:
1060:
1054:
1050:
1049:
1043:
1039:
1035:
1030:
1025:
1021:
1017:
1016:
1010:
1006:
1000:
996:
991:
987:
983:
979:
975:
971:
967:
962:
958:
954:
950:
946:
942:
938:
934:
930:
926:
923:
917:
913:
905:
901:
897:
893:
888:
883:
879:
875:
874:
868:
864:
860:
856:
850:
846:
842:
838:
833:
829:
823:
819:
818:
812:
807:
802:
798:
794:
793:
787:
786:
782:
775:
770:
767:
763:
758:
756:
752:
744:
740:
735:
732:
728:
723:
720:
716:
715:Kubale (2004)
712:
707:
704:
700:
695:
692:
688:
682:
679:
675:
670:
668:
664:
658:
656:
654:
651:
647:
643:
639:
634:
632:
628:
624:
620:
616:
612:
605:
603:
589:
584:
582:
578:
574:
570:
564:
560:
522:
518:
514:
510:
505:
491:
489:
487:
483:
477:
470:
442:
438:
437:Catlin (1979)
432:
413:
404:
402:
400:
399:list coloring
395:
373:
361:
352:
319:
303:
298:
258:
231:
217:
216:
215:
209:
208:constructible
193:
191:
187:
183:
170:
157:
155:
151:
150:Moser spindle
143:
139:
126:
88:
72:
71:Moser spindle
63:
57:
50:
48:
46:
42:
38:
34:
30:
26:
22:
1120:
1114:
1094:
1067:
1047:
1019:
1013:
994:
972:(1): 37–50,
969:
965:
940:
936:
929:Iwama, Kazuo
915:
911:
877:
871:
836:
817:Graph Theory
816:
796:
795:, Series B,
790:
769:
734:
722:
706:
694:
681:
642:Euler (2003)
635:
633:algorithms.
631:backtracking
609:
585:
577:Frege system
562:
558:
520:
516:
513:Hajós number
512:
506:
495:
482:dodecahedron
475:
468:
430:
411:
408:
396:
353:
307:
207:
197:
185:
181:
169:cycle graphs
158:
141:
127:
76:
61:
31:named after
24:
21:graph theory
18:
511:define the
297:contracting
240:be any two
1158:Categories
783:References
650:stable set
210:(or Hajós-
171:of length
136:each be a
1125:CiteSeerX
918:: 116–117
904:Hajós, G.
701:, p. 184.
488:vertices
486:antipodal
188:− 1
653:polytope
416:, every
351:colors.
198:A graph
1147:1341550
1103:0671913
1038:1144633
986:1658542
957:1336013
896:1388650
863:2163949
648:of the
556:edges,
263:be any
85:be two
35: (
1145:
1127:
1101:
1082:
1055:
1036:
1001:
984:
955:
894:
861:
851:
824:
646:facets
473:. For
97:, and
27:is an
659:Notes
573:co-NP
552:with
537:from
525:of a
443:that
1080:ISBN
1053:ISBN
999:ISBN
849:ISBN
822:ISBN
409:For
343:and
335:and
283:and
271:and
259:Let
248:and
236:and
232:Let
175:and
167:are
163:and
132:and
117:and
109:and
81:and
77:Let
37:1961
1135:doi
1072:doi
1024:doi
974:doi
945:doi
882:doi
878:152
841:doi
801:doi
636:In
579:in
478:= 4
471:≥ 4
433:= 8
414:= 3
299:it.
252:is
225:is
19:In
1160::
1143:MR
1141:,
1133:,
1119:,
1099:MR
1078:,
1034:MR
1032:,
1020:98
1018:,
982:MR
980:,
970:30
968:,
953:MR
951:,
941:54
939:,
931:;
916:10
914:,
892:MR
890:,
876:,
859:MR
857:,
847:,
797:26
754:^
713:;
666:^
655:.
640:,
583:.
504:.
394:.
329:wy
293:uv
190:.
184:+
125:.
123:wy
119:xy
115:vw
99:xy
91:vw
89:,
1150:.
1137::
1121:8
1106:.
1089:.
1074::
1062:.
1041:.
1026::
1008:.
989:.
976::
960:.
947::
924:.
908:n
899:.
884::
866:.
843::
831:.
810:.
803::
776:.
764:.
747:n
729:.
717:.
689:.
676:.
600:G
596:G
592:G
563:G
561:(
559:h
554:m
550:G
546:n
541:k
539:K
535:G
531:G
527:k
523:)
521:G
519:(
517:h
502:G
498:G
476:k
469:k
464:k
460:k
456:k
451:k
449:K
445:k
431:k
426:k
422:k
418:k
412:k
391:k
389:K
384:k
380:k
376:k
370:-
368:k
364:k
356:k
349:k
345:x
341:v
337:y
333:w
324:k
322:K
314:k
310:k
289:k
285:v
281:u
277:G
273:v
269:u
265:k
261:G
254:k
250:H
246:G
242:k
238:H
234:G
227:k
222:k
220:K
212:k
206:-
204:k
200:G
186:q
182:p
177:q
173:p
165:H
161:G
145:4
142:K
134:H
130:G
111:x
107:v
103:H
95:G
83:H
79:G
73:.
65:4
62:K
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
