38:
800:
1210:
397:
700:
356:
1151:
1093:
608:
475:
872:
634:
558:
532:
423:
320:
1171:
1117:
1063:
1036:
1016:
996:
972:
952:
932:
912:
892:
843:
823:
578:
502:
443:
317:
291:
268:
248:
228:
208:
179:
158:
138:
118:
96:
1126:
is a connected graph in which the deletion of any pair of adjacent vertices decreases the chromatic number by two. It is an open problem to determine whether
825:
may be decomposed into two smaller critical graphs, with an edge between every pair of vertices that includes one vertex from each of the two subgraphs, or
1271:
1495:
707:
1403:
41:
On the left-top a vertex critical graph with chromatic number 6; next all the N-1 subgraphs with chromatic number 5.
1241:
1202:
294:
1543:
1538:
1222:
1099:
with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require
478:
1259:
1182:
361:
327:
1096:
649:
1328:
1295:
31:
1227:
1311:
1437:
641:
332:
1491:
1267:
1517:
1412:
1340:
1303:
1232:
58:
54:
1424:
1129:
1071:
586:
448:
1420:
848:
613:
537:
511:
402:
187:
members in terms of chromatic number, which is a very important measure in graph theory.
1299:
1156:
1102:
1066:
1048:
1021:
1001:
981:
957:
937:
917:
897:
877:
828:
808:
581:
563:
487:
428:
302:
276:
253:
233:
213:
193:
164:
143:
123:
103:
81:
66:
1416:
1236:
974:
is the only vertex of its color and every other color class has at least two vertices.
37:
1532:
1463:
1315:
1206:
505:
69:
of the given graph. The decrease in the number of colors cannot be by more than one.
1505:
1379:
1357:
46:
65:, in the sense that its deletion would decrease the number of colors needed in a
637:
17:
1521:
1211:"A colour problem for infinite graphs and a problem in the theory of relations"
1344:
1307:
183:
if each of its vertices is a critical element. Critical graphs are the
1401:
Stehlík, Matěj (2003), "Critical graphs with connected complements",
1331:(1957), "A theorem of R. L. Brooks and a conjecture of H. Hadwiger",
36:
1446:
Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe
795:{\displaystyle 2m\geq (k-1)n+\lfloor (k-3)/(k^{2}-3)\rfloor n}
1286:
Brooks, R. L. (1941), "On colouring the nodes of a network",
894:
has a decomposition of this type, or for every vertex
1159:
1132:
1105:
1074:
1051:
1024:
1004:
984:
960:
940:
920:
900:
880:
851:
831:
811:
710:
652:
616:
589:
566:
540:
514:
490:
451:
431:
405:
364:
335:
305:
279:
256:
236:
216:
196:
167:
146:
126:
106:
84:
998:is vertex-critical if and only if for every vertex
1288:Proceedings of the Cambridge Philosophical Society
1165:
1145:
1111:
1087:
1057:
1030:
1010:
990:
966:
946:
926:
906:
886:
866:
837:
817:
794:
694:
628:
602:
572:
552:
526:
496:
469:
437:
417:
391:
350:
311:
285:
262:
242:
222:
202:
173:
152:
132:
112:
90:
399:. That is, every vertex is adjacent to at least
1018:, there is an optimal proper coloring in which
1333:Proceedings of the London Mathematical Society
534:, meaning every vertex is adjacent to exactly
61:. In such a graph, every vertex or edge is a
8:
1508:(6 August 2009), "On list critical graphs",
786:
741:
57:all of whose proper subgraphs have smaller
100:is a critical graph with chromatic number
1226:
1158:
1137:
1131:
1104:
1079:
1073:
1050:
1023:
1003:
983:
959:
939:
919:
899:
879:
850:
830:
810:
771:
759:
709:
651:
615:
594:
588:
565:
539:
513:
489:
450:
430:
404:
363:
334:
304:
278:
255:
235:
215:
195:
166:
145:
125:
105:
83:
1194:
1440:(1961), "Über eine Konstruktion nicht
1262:(1992), "Solution to Exercise 9.21",
1065:-critical graph may be formed from a
1042:
7:
1470:, Proc. Colloq., Tihany, p. 361
1384:Publ. Math. Inst. Hungar. Acad. Sci.
1362:Publ. Math. Inst. Hungar. Acad. Sci.
1264:Combinatorial Problems and Exercises
1215:Nederl. Akad. Wetensch. Proc. Ser. A
392:{\displaystyle \delta (G)\geq k-1}
25:
695:{\displaystyle 2m\geq (k-1)n+k-3}
1504:Stiebitz, Michael; Tuza, Zsolt;
1490:, New York: Wiley-Interscience,
1486:Jensen, T. R.; Toft, B. (1995),
1382:(1963), "Kritische Graphen II",
874:vertices. More strongly, either
1404:Journal of Combinatorial Theory
1360:(1963), "Kritische Graphen I",
1266:(2nd ed.), North-Holland,
1119:colors in any proper coloring.
783:
764:
756:
744:
732:
720:
674:
662:
464:
452:
374:
368:
345:
339:
1:
1417:10.1016/S0095-8956(03)00069-8
1237:10.1016/S1385-7258(51)50053-7
1153:is the only double-critical
1038:is a singleton color class.
30:Not to be confused with the
1516:(15), Elsevier: 4931–4941,
636:vertices, or an odd-length
1560:
1522:10.1016/j.disc.2008.05.021
351:{\displaystyle \delta (G)}
29:
1308:10.1017/S030500410002168X
1488:Graph coloring problems
1345:10.1112/plms/s3-7.1.161
425:others. More strongly,
321:de Bruijn–Erdős theorem
319:is finite (this is the
1167:
1147:
1113:
1089:
1059:
1032:
1012:
992:
968:
948:
928:
908:
888:
868:
839:
819:
796:
696:
630:
604:
574:
554:
528:
498:
471:
439:
419:
393:
352:
313:
287:
264:
244:
224:
204:
175:
154:
140:with chromatic number
134:
114:
92:
42:
34:in project management.
1466:(1967), "Problem 2",
1444:-färbbarer Graphen",
1183:Factor-critical graph
1168:
1148:
1146:{\displaystyle K_{k}}
1124:double-critical graph
1114:
1090:
1088:{\displaystyle K_{k}}
1060:
1033:
1013:
993:
969:
949:
929:
909:
889:
869:
840:
820:
797:
697:
631:
605:
603:{\displaystyle K_{k}}
575:
555:
529:
499:
472:
470:{\displaystyle (k-1)}
440:
420:
394:
358:obeys the inequality
353:
314:
288:
265:
245:
225:
205:
190:Some properties of a
176:
155:
135:
115:
93:
40:
1510:Discrete Mathematics
1157:
1130:
1103:
1072:
1049:
1022:
1002:
982:
958:
938:
918:
898:
878:
867:{\displaystyle 2k-1}
849:
829:
809:
708:
650:
614:
587:
564:
538:
512:
488:
449:
429:
403:
362:
333:
303:
277:
254:
234:
214:
194:
165:
144:
124:
104:
82:
32:Critical path method
1468:In Theory of Graphs
1300:1941PCPS...37..194B
954:-coloring in which
629:{\displaystyle n=k}
553:{\displaystyle k-1}
527:{\displaystyle k-1}
418:{\displaystyle k-1}
1173:-chromatic graph.
1163:
1143:
1109:
1097:Hajós construction
1085:
1055:
1028:
1008:
988:
964:
944:
924:
904:
884:
864:
835:
815:
792:
692:
626:
600:
570:
550:
524:
494:
467:
435:
415:
389:
348:
309:
283:
260:
240:
220:
200:
171:
150:
130:
110:
88:
43:
1273:978-0-8218-6947-5
1166:{\displaystyle k}
1112:{\displaystyle k}
1095:by combining the
1058:{\displaystyle k}
1031:{\displaystyle v}
1011:{\displaystyle v}
991:{\displaystyle G}
967:{\displaystyle v}
947:{\displaystyle k}
927:{\displaystyle G}
907:{\displaystyle v}
887:{\displaystyle G}
838:{\displaystyle G}
818:{\displaystyle G}
573:{\displaystyle G}
497:{\displaystyle G}
438:{\displaystyle G}
312:{\displaystyle G}
286:{\displaystyle G}
263:{\displaystyle m}
243:{\displaystyle n}
223:{\displaystyle G}
203:{\displaystyle k}
174:{\displaystyle k}
153:{\displaystyle k}
133:{\displaystyle G}
113:{\displaystyle k}
91:{\displaystyle k}
16:(Redirected from
1551:
1524:
1500:
1472:
1471:
1460:
1454:
1453:
1443:
1434:
1428:
1427:
1398:
1392:
1391:
1376:
1370:
1369:
1354:
1348:
1347:
1325:
1319:
1318:
1283:
1277:
1276:
1256:
1250:
1239:
1230:
1203:de Bruijn, N. G.
1199:
1172:
1170:
1169:
1164:
1152:
1150:
1149:
1144:
1142:
1141:
1118:
1116:
1115:
1110:
1094:
1092:
1091:
1086:
1084:
1083:
1064:
1062:
1061:
1056:
1037:
1035:
1034:
1029:
1017:
1015:
1014:
1009:
997:
995:
994:
989:
973:
971:
970:
965:
953:
951:
950:
945:
933:
931:
930:
925:
913:
911:
910:
905:
893:
891:
890:
885:
873:
871:
870:
865:
844:
842:
841:
836:
824:
822:
821:
816:
801:
799:
798:
793:
776:
775:
763:
701:
699:
698:
693:
635:
633:
632:
627:
609:
607:
606:
601:
599:
598:
579:
577:
576:
571:
559:
557:
556:
551:
533:
531:
530:
525:
503:
501:
500:
495:
476:
474:
473:
468:
444:
442:
441:
436:
424:
422:
421:
416:
398:
396:
395:
390:
357:
355:
354:
349:
318:
316:
315:
310:
292:
290:
289:
284:
269:
267:
266:
261:
249:
247:
246:
241:
229:
227:
226:
221:
210:-critical graph
209:
207:
206:
201:
181:-vertex-critical
180:
178:
177:
172:
159:
157:
156:
151:
139:
137:
136:
131:
119:
117:
116:
111:
97:
95:
94:
89:
63:critical element
59:chromatic number
55:undirected graph
27:Undirected graph
21:
18:Critical element
1559:
1558:
1554:
1553:
1552:
1550:
1549:
1548:
1529:
1528:
1527:
1503:
1498:
1485:
1481:
1479:Further reading
1476:
1475:
1462:
1461:
1457:
1441:
1436:
1435:
1431:
1400:
1399:
1395:
1378:
1377:
1373:
1356:
1355:
1351:
1327:
1326:
1322:
1285:
1284:
1280:
1274:
1258:
1257:
1253:
1228:10.1.1.210.6623
1201:
1200:
1196:
1191:
1179:
1155:
1154:
1133:
1128:
1127:
1101:
1100:
1075:
1070:
1069:
1047:
1046:
1020:
1019:
1000:
999:
980:
979:
956:
955:
936:
935:
916:
915:
896:
895:
876:
875:
847:
846:
827:
826:
807:
806:
767:
706:
705:
648:
647:
642:Brooks' theorem
612:
611:
590:
585:
584:
562:
561:
536:
535:
510:
509:
486:
485:
447:
446:
427:
426:
401:
400:
360:
359:
331:
330:
301:
300:
275:
274:
252:
251:
232:
231:
212:
211:
192:
191:
163:
162:
142:
141:
122:
121:
102:
101:
98:-critical graph
80:
79:
75:
35:
28:
23:
22:
15:
12:
11:
5:
1557:
1555:
1547:
1546:
1544:Graph coloring
1541:
1539:Graph families
1531:
1530:
1526:
1525:
1501:
1496:
1482:
1480:
1477:
1474:
1473:
1455:
1429:
1411:(2): 189–194,
1393:
1371:
1349:
1339:(1): 161–195,
1320:
1294:(2): 194–197,
1278:
1272:
1260:Lovász, László
1251:
1193:
1192:
1190:
1187:
1186:
1185:
1178:
1175:
1162:
1140:
1136:
1108:
1082:
1078:
1067:complete graph
1054:
1045:showed, every
1027:
1007:
987:
976:
975:
963:
943:
923:
903:
883:
863:
860:
857:
854:
834:
814:
803:
791:
788:
785:
782:
779:
774:
770:
766:
762:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
703:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
645:
625:
622:
619:
597:
593:
582:complete graph
580:is either the
569:
549:
546:
543:
523:
520:
517:
493:
482:
479:edge-connected
466:
463:
460:
457:
454:
434:
414:
411:
408:
388:
385:
382:
379:
376:
373:
370:
367:
347:
344:
341:
338:
324:
308:
298:
282:
259:
239:
219:
199:
170:
149:
129:
109:
87:
74:
71:
67:graph coloring
51:critical graph
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1556:
1545:
1542:
1540:
1537:
1536:
1534:
1523:
1519:
1515:
1511:
1507:
1506:Voigt, Margit
1502:
1499:
1497:0-471-02865-7
1493:
1489:
1484:
1483:
1478:
1469:
1465:
1459:
1456:
1451:
1447:
1439:
1433:
1430:
1426:
1422:
1418:
1414:
1410:
1406:
1405:
1397:
1394:
1389:
1385:
1381:
1375:
1372:
1367:
1363:
1359:
1353:
1350:
1346:
1342:
1338:
1334:
1330:
1324:
1321:
1317:
1313:
1309:
1305:
1301:
1297:
1293:
1289:
1282:
1279:
1275:
1269:
1265:
1261:
1255:
1252:
1248:
1245:
1244:
1238:
1234:
1229:
1224:
1220:
1216:
1212:
1208:
1204:
1198:
1195:
1188:
1184:
1181:
1180:
1176:
1174:
1160:
1138:
1134:
1125:
1120:
1106:
1098:
1080:
1076:
1068:
1052:
1044:
1039:
1025:
1005:
985:
961:
941:
921:
901:
881:
861:
858:
855:
852:
845:has at least
832:
812:
804:
789:
780:
777:
772:
768:
760:
753:
750:
747:
738:
735:
729:
726:
723:
717:
714:
711:
704:
689:
686:
683:
680:
677:
671:
668:
665:
659:
656:
653:
646:
643:
639:
623:
620:
617:
595:
591:
583:
567:
560:others, then
547:
544:
541:
521:
518:
515:
507:
506:regular graph
491:
483:
480:
461:
458:
455:
432:
412:
409:
406:
386:
383:
380:
377:
371:
365:
342:
336:
329:
325:
322:
306:
299:
296:
293:has only one
280:
273:
272:
271:
257:
250:vertices and
237:
217:
197:
188:
186:
182:
168:
147:
127:
107:
99:
85:
72:
70:
68:
64:
60:
56:
52:
48:
39:
33:
19:
1513:
1509:
1487:
1467:
1458:
1449:
1445:
1432:
1408:
1407:, Series B,
1402:
1396:
1387:
1383:
1374:
1365:
1361:
1352:
1336:
1332:
1329:Dirac, G. A.
1323:
1291:
1287:
1281:
1263:
1254:
1246:
1243:Indag. Math.
1242:
1218:
1214:
1197:
1123:
1121:
1043:Hajós (1961)
1040:
977:
508:with degree
326:The minimum
189:
184:
161:
78:
76:
62:
50:
47:graph theory
44:
1464:Erdős, Paul
1221:: 371–373,
934:there is a
638:cycle graph
1533:Categories
1380:Gallai, T.
1358:Gallai, T.
1189:References
640:. This is
120:. A graph
73:Variations
1452:: 116–117
1438:Hajós, G.
1390:: 373–395
1368:: 165–192
1316:209835194
1223:CiteSeerX
1207:Erdős, P.
859:−
787:⌋
778:−
751:−
742:⌊
727:−
718:≥
687:−
669:−
660:≥
545:−
519:−
459:−
410:−
384:−
378:≥
366:δ
337:δ
295:component
1209:(1951),
1177:See also
1425:2017723
1296:Bibcode
805:Either
270:edges:
185:minimal
1494:
1423:
1314:
1270:
1225:
978:Graph
328:degree
53:is an
1312:S2CID
610:with
504:is a
230:with
1492:ISBN
1268:ISBN
1240:. (
49:, a
1518:doi
1514:309
1413:doi
1341:doi
1304:doi
1233:doi
1041:As
914:of
484:If
445:is
160:is
45:In
1535::
1512:,
1450:10
1448:,
1421:MR
1419:,
1409:89
1386:,
1364:,
1335:,
1310:,
1302:,
1292:37
1290:,
1249:.)
1247:13
1231:,
1219:54
1217:,
1213:,
1205:;
1122:A
323:).
77:A
1520::
1442:n
1415::
1388:8
1366:8
1343::
1337:7
1306::
1298::
1235::
1161:k
1139:k
1135:K
1107:k
1081:k
1077:K
1053:k
1026:v
1006:v
986:G
962:v
942:k
922:G
902:v
882:G
862:1
856:k
853:2
833:G
813:G
802:.
790:n
784:)
781:3
773:2
769:k
765:(
761:/
757:)
754:3
748:k
745:(
739:+
736:n
733:)
730:1
724:k
721:(
715:m
712:2
702:.
690:3
684:k
681:+
678:n
675:)
672:1
666:k
663:(
657:m
654:2
644:.
624:k
621:=
618:n
596:k
592:K
568:G
548:1
542:k
522:1
516:k
492:G
481:.
477:-
465:)
462:1
456:k
453:(
433:G
413:1
407:k
387:1
381:k
375:)
372:G
369:(
346:)
343:G
340:(
307:G
297:.
281:G
258:m
238:n
218:G
198:k
169:k
148:k
128:G
108:k
86:k
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
