422:
2529:, Goddard, W., and Jesurum, C. E. 1997. Coloring with defect. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Louisiana, United States, January 05–07, 1997). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 548–557.
41:
Defective coloring was introduced nearly simultaneously by Burr and
Jacobson, Harary and Jones and Cowen, Cowen and Woodall. Surveys of this and related colorings are given by Marietjie Frick. Cowen, Cowen and Woodall focused on graphs embedded on surfaces and gave a complete characterization of all
2163:
An example of an application of defective colouring is the scheduling problem where vertices represent jobs (say users on a computer system), and edges represent conflicts (needing to access one or more of the same files). Allowing a defect means tolerating some threshold of conflict: each user may
74:, this solves defective chromatic number for the plane. Poh and Goddard showed that any planar graph has a special (3,2)-coloring in which each color class is a linear forest, and this can be obtained from a more general result of Woodall. For general surfaces, it was shown that for each genus
28:
is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent. (See here for
2875:
Angelini, Patrizio; Bekos, Michael; De Luca, Felice; Didimo, Walter; Kaufmann, Michael; Kobourov, Stephen; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Roselli, Vincenzo; Symvonis, Antonios (2017), "Vertex-Coloring with
Defects",
1439:
1248:
656:
2588:
Angelini, Patrizio; Bekos, Michael; De Luca, Felice; Didimo, Walter; Kaufmann, Michael; Kobourov, Stephen; Montecchiani, Fabrizio; Raftopoulou, Chrysanthi; Roselli, Vincenzo; Symvonis, Antonios (2017).
1146:
539:
988:
1738:
1551:
as a subgraph. But every subgraph of an outerplanar graph is outerplanar and every graph obtained by contracting edges of an outerplanar graph is outerplanar. This implies that
589:
300:
2105:
1693:
1582:
1549:
1516:
1464:
1362:
1333:
1273:
1171:
1075:
98:
337:)-colourable. For example, the defective chromatic number of the class of planar graphs equals 3, since every planar graph is (3,2)-colourable and for every integer
133:
2067:
1912:
1885:
1858:
1765:
1660:
1609:
1491:
1300:
1042:
1015:
955:
928:
861:
814:
454:
70:)-colorable; there exist planar graphs which are not (3, 1)-colorable, but every planar graph is (3, 2)-colorable. Together with the (4, 0)-coloring implied by the
2153:
2133:
2040:
2020:
2000:
1972:
1952:
1932:
1831:
1805:
1785:
1629:
901:
881:
834:
787:
421:
153:
2164:
find the maximum slowdown incurred for retrieval of data with two conflicting other users on the system acceptable, and with more than two unacceptable.
2747:
L. J. Cowen; R. H. Cowen; D. R. Woodall (3 Oct 2006), "Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency",
2829:
Borodin, O.V; Kostochka, A.V (Oct–Dec 1977), "On an upper bound of a graph's chromatic number, depending on the graph's degree and density",
1367:
1176:
2199:; Cowen, R. H.; Woodall, D. R. (3 Oct 2006). "Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency".
2480:
2738:
2638:
2243:
595:
2831:
2392:
2294:
698:
2913:
1080:
473:
679:
30:
2908:
2261:
960:
2690:
2668:
2466:
1698:
168:
545:
2703:
Frick, Marietjie; Henning, Michael (March 1994), "Extremal results on defective colorings of graphs",
2695:
2673:
2471:
269:
2570:
2552:
71:
456:, is as shown in the figure. The first subfigure is an example of proper vertex colouring or a (
2734:
2634:
2388:"On an upper bound of a graph's chromatic number, depending on the graph's degree and density"
2239:
759:
2853:
Lawrence, Jim (1978), "Covering the vertex set of a graph with subgraphs of smaller degree",
2072:
1665:
1554:
1521:
1305:
1047:
77:
2885:
2862:
2840:
2816:
2796:
2776:
2756:
2712:
2602:
2562:
2507:
2476:
2434:
2401:
2366:
2335:
2303:
2270:
2231:
2208:
1336:
103:
2045:
1890:
1863:
1836:
1743:
1638:
1587:
1469:
1278:
1020:
993:
933:
906:
839:
792:
432:
2115:
Defective coloring is computationally hard. It is NP-complete to decide if a given graph
1496:
1444:
1342:
1253:
1151:
2323:
2138:
2118:
2025:
2005:
1985:
1957:
1937:
1917:
1816:
1790:
1770:
1614:
886:
866:
819:
772:
164:
138:
21:
2235:
24:
refers to an assignment of colours or labels to vertices, edges and faces of a graph.
2902:
2867:
2845:
2821:
2717:
2512:
2495:
2439:
2422:
2406:
2387:
2371:
2354:
2308:
2289:
701:, while each colour class in a defective coloring forms a subgraph of degree at most
2574:
2731:
SODA '97 Proceedings of the Eighth Annual ACM-SIAM Symposium on
Discrete Algorithms
2659:
Eaton, Nancy J.; Hull, Thomas (1999), "Defective list colorings of planar graphs",
2631:
SODA '97 Proceedings of the Eighth Annual ACM-SIAM Symposium on
Discrete Algorithms
2622:
2526:
2454:
2196:
17:
697:
In graph theoretic terms, each colour class in a proper vertex coloring forms an
2540:
2767:
Archdeacon, Dan (1987), "A note on defective colorings of graphs in surfaces",
2787:
Poh, K. S. (March 1990), "On the linear vertex-arboricity of a planar graph",
2259:
Poh, K. S. (March 1990). "On the linear vertex-arboricity of a planar graph".
2800:
2780:
2760:
2726:
2626:
2339:
2274:
2212:
2191:
2189:
2187:
2185:
2183:
2181:
2179:
2177:
425:
Example of defective colouring of a cycle on five vertices when d = 0, 1, 2
220:
to be a positive integer (it is inconsequential to consider the case when
2481:
10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T
2890:
2607:
2590:
2566:
2457:; Goddard, W.; Jesurum, C. E. (1997). "Defective coloring revisited".
2423:"Covering the vertex set of a graph with subgraphs of smaller degree"
2155:
is of maximum vertex-degree 6 or planar of maximum vertex-degree 7.
1787:
is odd and red if even. Hence, we have produced a (2,2)-coloring of
2807:
Goddard, Wayne (7 Aug 1991), "Acyclic colorings of planar graphs",
1466:
is replaced by a single vertex that is adjacent to every vertex in
1434:{\displaystyle \langle V_{0}\cup V_{1}\cup ...\cup V_{i-1}\rangle }
1243:{\displaystyle \langle V_{0}\cup V_{1}\cup ...\cup V_{i-1}\rangle }
175:-time algorithm for defective coloring graphs of maximum degree ∆.
171:
from the 1960s, which has been rediscovered many times provides a
2557:
420:
2681:
William, W.; Hull, Thomas (2002), "Defective
Circular Coloring",
2230:. Annals of Discrete Mathematics. Vol. 55. pp. 45–57.
2543:; Seymour, Paul (2015). "A Relative of Hadwiger's Conjecture".
2326:(1987). "A note on defective colorings of graphs in surfaces".
429:
An example of defective colouring of a cycle on five vertices,
651:{\displaystyle \chi _{2}(C_{n})=1;\forall n\in \mathbb {N} }
232:, 0)-coloring is equivalent to proper vertex coloring.
413:. Hence, the impropriety of a proper vertex coloring is 0.
464:, 1)-coloring and the third subfigure is an example of a (
2725:
L. J. Cowen; W. Goddard; C. E. Jesurum (5 January 1997),
2226:
Frick, Marietjie (1993). "A Survey of (M, k)-Colorings".
1044:
contains a vertex of degree 3 or more, then it contains
460:, 0)-coloring. The second subfigure is an example of a (
409:
is the maximum of the improprieties of all vertices of
666:
It is enough to consider connected graphs, as a graph
2141:
2121:
2075:
2048:
2028:
2008:
1988:
1960:
1940:
1920:
1893:
1866:
1839:
1819:
1793:
1773:
1746:
1701:
1668:
1641:
1617:
1611:
contains a vertex of degree 3 or more, implying that
1590:
1557:
1524:
1499:
1472:
1447:
1370:
1345:
1308:
1281:
1256:
1179:
1154:
1083:
1050:
1023:
996:
963:
936:
909:
889:
869:
842:
822:
795:
775:
598:
548:
476:
435:
272:
141:
106:
80:
2539:Edwards, Katherine; Kang, Dong Yeap; Kim, Jaehoon;
2496:"Extremal results on defective colorings of graphs"
1141:{\displaystyle V_{0}\cup V_{1}\cup ...\cup V_{i-1}}
2147:
2127:
2099:
2061:
2034:
2014:
1994:
1966:
1946:
1926:
1906:
1879:
1852:
1825:
1799:
1779:
1759:
1732:
1687:
1654:
1623:
1603:
1576:
1543:
1510:
1485:
1458:
1433:
1356:
1327:
1294:
1267:
1242:
1165:
1140:
1069:
1036:
1009:
982:
949:
922:
895:
875:
855:
828:
808:
781:
650:
583:
533:
448:
294:
147:
127:
92:
2494:Frick, Marietjie; Henning, Michael (March 1994).
1811:Corollary: Every planar graph is (4,2)-colorable.
2625:; Goddard, W.; Jesurum, C. E. (5 January 1997).
2135:admits a (3,1)-coloring, even in the case where
1584:is outerplanar, a contradiction. Hence no graph
212:neighbours having the same colour as the vertex
2355:"On a theorem about vertex colorings of graphs"
1887:is (2,2)-colourable. Therefore, each vertex of
534:{\displaystyle \chi _{0}(C_{5})=\chi (C_{5})=3}
135:such that every graph on the surface of genus
2386:Borodin, O.V; Kostochka, A.V (Oct–Dec 1977).
1077:as a subgraph. Then we contract all edges of
8:
2878:Journal of Graph Algorithms and Applications
2595:Journal of Graph Algorithms and Applications
1954:is odd, hence producing a (4,2)-coloring of
1860:(same as above) is outerplanar. Hence every
1428:
1371:
1237:
1180:
977:
964:
58:)-colorable. Namely, there does not exist a
2889:
2866:
2844:
2820:
2716:
2694:
2672:
2606:
2556:
2511:
2470:
2438:
2405:
2370:
2307:
2140:
2120:
2074:
2053:
2047:
2027:
2007:
1987:
1959:
1939:
1919:
1898:
1892:
1871:
1865:
1844:
1838:
1818:
1792:
1772:
1751:
1745:
1706:
1700:
1673:
1667:
1646:
1640:
1616:
1595:
1589:
1562:
1556:
1529:
1523:
1498:
1477:
1471:
1446:
1416:
1391:
1378:
1369:
1344:
1339:all the edges mentioned above, we obtain
1313:
1307:
1286:
1280:
1255:
1225:
1200:
1187:
1178:
1153:
1126:
1101:
1088:
1082:
1055:
1049:
1028:
1022:
1001:
995:
971:
962:
941:
935:
914:
908:
888:
868:
847:
841:
821:
800:
794:
774:
644:
643:
616:
603:
597:
566:
553:
547:
516:
494:
481:
475:
440:
434:
277:
271:
140:
105:
79:
2173:
341:there is a planar graph that is not (2,
789:be a connected outerplanar graph. Let
228:to be a non-negative integer. Hence, (
159:)-colorable. This was improved to (3,
983:{\displaystyle \langle V_{i}\rangle }
7:
2545:SIAM Journal on Discrete Mathematics
2290:"Acyclic colorings of planar graphs"
1733:{\displaystyle V_{i+1},i\geqslant 1}
62:such that every planar graph is (1,
200:is a coloring of its vertices with
678:)-colourable if and only if every
634:
584:{\displaystyle \chi _{1}(C_{5})=3}
167:. For general graphs, a result of
14:
1978:Graphs excluding a complete minor
2353:Bernardi, Claudio (March 1987).
1275:is connected as every vertex in
401:be a vertex-coloring of a graph
393:Impropriety of a vertex-coloring
389:is said to be properly colored.
357:be a vertex-coloring of a graph
2832:Journal of Combinatorial Theory
2393:Journal of Combinatorial Theory
1934:is even and green or yellow if
373:is the number of neighbours of
2094:
2076:
1914:can be colored blue or red if
622:
609:
572:
559:
522:
509:
500:
487:
361:. The impropriety of a vertex
289:
283:
243:The minimum number of colours
204:colours such that each vertex
122:
116:
1:
2591:"VertexColoring with Defects"
2288:Goddard, Wayne (7 Aug 1991).
2236:10.1016/S0167-5060(08)70374-1
1662:is adjacent to any vertex of
1635:, 2)-colorable. No vertex of
369:with respect to the coloring
20:, a mathematical discipline,
2868:10.1016/0012-365X(78)90147-4
2846:10.1016/0095-8956(77)90037-5
2822:10.1016/0012-365X(91)90166-Y
2718:10.1016/0012-365X(94)90260-7
2513:10.1016/0012-365X(94)90260-7
2440:10.1016/0012-365X(78)90147-4
2407:10.1016/0095-8956(77)90037-5
2372:10.1016/0012-365X(87)90243-3
2309:10.1016/0012-365X(91)90166-Y
724:)-colourable for each pair (
377:that have the same color as
295:{\displaystyle \chi _{d}(G)}
2228:A Survey of (m,k)-Colorings
1302:is adjacent to a vertex in
321:such that for some integer
264:-defective chromatic number
259:)-colourable is called the
239:-defective chromatic number
179:Definitions and terminology
50:such that every planar is (
2930:
990:, the subgraph induced by
863:be the set of vertices of
816:be an arbitrary vertex of
716:)-colourable, then it is (
468:, 2)-coloring. Note that,
311:defective chromatic number
1173:. It is to be noted that
2661:Bull. Inst. Combin. Appl
2111:Computational complexity
1740:, hence the vertices of
381:. If the impropriety of
31:Glossary of graph theory
2789:Journal of Graph Theory
2769:Journal of Graph Theory
2749:Journal of Graph Theory
2683:Austr. J. Combinatorics
2459:Journal of Graph Theory
2328:Journal of Graph Theory
2262:Journal of Graph Theory
2201:Journal of Graph Theory
2100:{\displaystyle (t-1,N)}
1767:can be colored blue if
1688:{\displaystyle V_{i-1}}
1577:{\displaystyle K_{2,3}}
1544:{\displaystyle K_{2,3}}
1364:such that the subgraph
1328:{\displaystyle V_{i-1}}
1070:{\displaystyle K_{1,3}}
883:that are at a distance
349:Impropriety of a vertex
93:{\displaystyle g\geq 0}
2801:10.1002/jgt.3190140108
2781:10.1002/jgt.3190110408
2761:10.1002/jgt.3190100207
2727:"Coloring with defect"
2627:"Coloring with defect"
2421:Lawrence, Jim (1978).
2340:10.1002/jgt.3190110408
2275:10.1002/jgt.3190140108
2213:10.1002/jgt.3190100207
2149:
2129:
2101:
2063:
2036:
2022:such that every graph
2016:
1996:
1968:
1948:
1928:
1908:
1881:
1854:
1827:
1801:
1781:
1761:
1734:
1689:
1656:
1625:
1605:
1578:
1545:
1512:
1487:
1460:
1435:
1358:
1329:
1296:
1269:
1244:
1167:
1148:to obtain a new graph
1142:
1071:
1038:
1011:
984:
951:
924:
897:
877:
857:
830:
810:
783:
652:
585:
535:
450:
426:
296:
196:)-coloring of a graph
149:
129:
128:{\displaystyle k=k(g)}
94:
2150:
2130:
2102:
2064:
2062:{\displaystyle K_{t}}
2037:
2017:
1997:
1969:
1949:
1929:
1909:
1907:{\displaystyle V_{i}}
1882:
1880:{\displaystyle G_{i}}
1855:
1853:{\displaystyle G_{i}}
1833:is planar then every
1828:
1802:
1782:
1762:
1760:{\displaystyle V_{i}}
1735:
1690:
1657:
1655:{\displaystyle V_{i}}
1626:
1606:
1604:{\displaystyle G_{i}}
1579:
1546:
1513:
1488:
1486:{\displaystyle V_{i}}
1461:
1436:
1359:
1330:
1297:
1295:{\displaystyle V_{i}}
1270:
1245:
1168:
1143:
1072:
1039:
1037:{\displaystyle G_{i}}
1012:
1010:{\displaystyle V_{i}}
985:
952:
950:{\displaystyle G_{i}}
925:
923:{\displaystyle v_{0}}
898:
878:
858:
856:{\displaystyle V_{i}}
831:
811:
809:{\displaystyle v_{0}}
784:
653:
586:
536:
451:
449:{\displaystyle C_{5}}
424:
405:. The impropriety of
297:
150:
130:
95:
2914:NP-complete problems
2855:Discrete Mathematics
2809:Discrete Mathematics
2705:Discrete Mathematics
2500:Discrete Mathematics
2427:Discrete Mathematics
2359:Discrete Mathematics
2295:Discrete Mathematics
2139:
2119:
2073:
2046:
2026:
2006:
2002:there is an integer
1986:
1958:
1938:
1918:
1891:
1864:
1837:
1817:
1791:
1771:
1744:
1699:
1666:
1639:
1615:
1588:
1555:
1522:
1497:
1470:
1445:
1368:
1343:
1306:
1279:
1254:
1177:
1152:
1081:
1048:
1021:
994:
961:
934:
907:
887:
867:
840:
820:
793:
773:
596:
546:
474:
433:
270:
139:
104:
78:
1813:This follows as if
680:connected component
317:is minimum integer
247:required for which
2891:10.7155/jgaa.00418
2608:10.7155/jgaa.00418
2145:
2125:
2097:
2059:
2032:
2012:
1992:
1982:For every integer
1964:
1944:
1924:
1904:
1877:
1850:
1823:
1797:
1777:
1757:
1730:
1685:
1652:
1621:
1601:
1574:
1541:
1511:{\displaystyle G'}
1508:
1483:
1459:{\displaystyle G'}
1456:
1431:
1357:{\displaystyle G'}
1354:
1325:
1292:
1268:{\displaystyle G'}
1265:
1240:
1166:{\displaystyle G'}
1163:
1138:
1067:
1034:
1007:
980:
947:
920:
893:
873:
853:
826:
806:
779:
762:is (2,2)-colorable
648:
581:
531:
446:
427:
305:For a graph class
292:
184:Defective coloring
145:
125:
90:
72:four color theorem
26:Defective coloring
2567:10.1137/141002177
2148:{\displaystyle G}
2128:{\displaystyle G}
2035:{\displaystyle G}
2015:{\displaystyle N}
1995:{\displaystyle t}
1967:{\displaystyle G}
1947:{\displaystyle i}
1927:{\displaystyle i}
1826:{\displaystyle G}
1800:{\displaystyle G}
1780:{\displaystyle i}
1624:{\displaystyle G}
896:{\displaystyle i}
876:{\displaystyle G}
829:{\displaystyle G}
782:{\displaystyle G}
760:outerplanar graph
325:, every graph in
148:{\displaystyle g}
100:, there exists a
2921:
2894:
2893:
2871:
2870:
2849:
2848:
2839:(2–3): 247–250,
2825:
2824:
2803:
2783:
2763:
2743:
2721:
2720:
2711:(1–3): 151–158,
2699:
2698:
2677:
2676:
2645:
2644:
2619:
2613:
2612:
2610:
2585:
2579:
2578:
2560:
2551:(4): 2385–2388.
2536:
2530:
2524:
2518:
2517:
2515:
2506:(1–3): 151–158.
2491:
2485:
2484:
2474:
2451:
2445:
2444:
2442:
2418:
2412:
2411:
2409:
2400:(2–3): 247–250.
2383:
2377:
2376:
2374:
2350:
2344:
2343:
2320:
2314:
2313:
2311:
2285:
2279:
2278:
2256:
2250:
2249:
2223:
2217:
2216:
2193:
2154:
2152:
2151:
2146:
2134:
2132:
2131:
2126:
2106:
2104:
2103:
2098:
2068:
2066:
2065:
2060:
2058:
2057:
2041:
2039:
2038:
2033:
2021:
2019:
2018:
2013:
2001:
1999:
1998:
1993:
1973:
1971:
1970:
1965:
1953:
1951:
1950:
1945:
1933:
1931:
1930:
1925:
1913:
1911:
1910:
1905:
1903:
1902:
1886:
1884:
1883:
1878:
1876:
1875:
1859:
1857:
1856:
1851:
1849:
1848:
1832:
1830:
1829:
1824:
1806:
1804:
1803:
1798:
1786:
1784:
1783:
1778:
1766:
1764:
1763:
1758:
1756:
1755:
1739:
1737:
1736:
1731:
1717:
1716:
1694:
1692:
1691:
1686:
1684:
1683:
1661:
1659:
1658:
1653:
1651:
1650:
1630:
1628:
1627:
1622:
1610:
1608:
1607:
1602:
1600:
1599:
1583:
1581:
1580:
1575:
1573:
1572:
1550:
1548:
1547:
1542:
1540:
1539:
1517:
1515:
1514:
1509:
1507:
1492:
1490:
1489:
1484:
1482:
1481:
1465:
1463:
1462:
1457:
1455:
1440:
1438:
1437:
1432:
1427:
1426:
1396:
1395:
1383:
1382:
1363:
1361:
1360:
1355:
1353:
1334:
1332:
1331:
1326:
1324:
1323:
1301:
1299:
1298:
1293:
1291:
1290:
1274:
1272:
1271:
1266:
1264:
1249:
1247:
1246:
1241:
1236:
1235:
1205:
1204:
1192:
1191:
1172:
1170:
1169:
1164:
1162:
1147:
1145:
1144:
1139:
1137:
1136:
1106:
1105:
1093:
1092:
1076:
1074:
1073:
1068:
1066:
1065:
1043:
1041:
1040:
1035:
1033:
1032:
1016:
1014:
1013:
1008:
1006:
1005:
989:
987:
986:
981:
976:
975:
956:
954:
953:
948:
946:
945:
929:
927:
926:
921:
919:
918:
902:
900:
899:
894:
882:
880:
879:
874:
862:
860:
859:
854:
852:
851:
835:
833:
832:
827:
815:
813:
812:
807:
805:
804:
788:
786:
785:
780:
657:
655:
654:
649:
647:
621:
620:
608:
607:
590:
588:
587:
582:
571:
570:
558:
557:
540:
538:
537:
532:
521:
520:
499:
498:
486:
485:
455:
453:
452:
447:
445:
444:
301:
299:
298:
293:
282:
281:
154:
152:
151:
146:
134:
132:
131:
126:
99:
97:
96:
91:
2929:
2928:
2924:
2923:
2922:
2920:
2919:
2918:
2899:
2898:
2897:
2874:
2852:
2828:
2806:
2786:
2766:
2746:
2741:
2724:
2702:
2680:
2658:
2654:
2649:
2648:
2641:
2621:
2620:
2616:
2587:
2586:
2582:
2538:
2537:
2533:
2525:
2521:
2493:
2492:
2488:
2453:
2452:
2448:
2420:
2419:
2415:
2385:
2384:
2380:
2352:
2351:
2347:
2324:Archdeacon, Dan
2322:
2321:
2317:
2287:
2286:
2282:
2258:
2257:
2253:
2246:
2225:
2224:
2220:
2195:
2194:
2175:
2170:
2161:
2137:
2136:
2117:
2116:
2113:
2071:
2070:
2049:
2044:
2043:
2024:
2023:
2004:
2003:
1984:
1983:
1980:
1956:
1955:
1936:
1935:
1916:
1915:
1894:
1889:
1888:
1867:
1862:
1861:
1840:
1835:
1834:
1815:
1814:
1789:
1788:
1769:
1768:
1747:
1742:
1741:
1702:
1697:
1696:
1669:
1664:
1663:
1642:
1637:
1636:
1613:
1612:
1591:
1586:
1585:
1558:
1553:
1552:
1525:
1520:
1519:
1500:
1495:
1494:
1473:
1468:
1467:
1448:
1443:
1442:
1412:
1387:
1374:
1366:
1365:
1346:
1341:
1340:
1309:
1304:
1303:
1282:
1277:
1276:
1257:
1252:
1251:
1221:
1196:
1183:
1175:
1174:
1155:
1150:
1149:
1122:
1097:
1084:
1079:
1078:
1051:
1046:
1045:
1024:
1019:
1018:
997:
992:
991:
967:
959:
958:
937:
932:
931:
910:
905:
904:
885:
884:
865:
864:
843:
838:
837:
818:
817:
796:
791:
790:
771:
770:
764:
755:
708:If a graph is (
699:independent set
663:
612:
599:
594:
593:
562:
549:
544:
543:
512:
490:
477:
472:
471:
436:
431:
430:
419:
395:
351:
273:
268:
267:
241:
186:
181:
163:)-colorable by
137:
136:
102:
101:
76:
75:
39:
12:
11:
5:
2927:
2925:
2917:
2916:
2911:
2909:Graph coloring
2901:
2900:
2896:
2895:
2884:(3): 313–340,
2872:
2850:
2826:
2804:
2784:
2775:(4): 517–519,
2764:
2755:(2): 187–195,
2744:
2739:
2722:
2700:
2696:10.1.1.91.4722
2678:
2674:10.1.1.91.4722
2655:
2653:
2650:
2647:
2646:
2639:
2614:
2601:(3): 313–340.
2580:
2531:
2519:
2486:
2472:10.1.1.52.3835
2465:(3): 205–219.
2446:
2413:
2378:
2345:
2334:(4): 517–519.
2315:
2280:
2251:
2244:
2218:
2207:(2): 187–195.
2172:
2171:
2169:
2166:
2160:
2157:
2144:
2124:
2112:
2109:
2096:
2093:
2090:
2087:
2084:
2081:
2078:
2056:
2052:
2031:
2011:
1991:
1979:
1976:
1963:
1943:
1923:
1901:
1897:
1874:
1870:
1847:
1843:
1822:
1796:
1776:
1754:
1750:
1729:
1726:
1723:
1720:
1715:
1712:
1709:
1705:
1682:
1679:
1676:
1672:
1649:
1645:
1620:
1598:
1594:
1571:
1568:
1565:
1561:
1538:
1535:
1532:
1528:
1506:
1503:
1480:
1476:
1454:
1451:
1430:
1425:
1422:
1419:
1415:
1411:
1408:
1405:
1402:
1399:
1394:
1390:
1386:
1381:
1377:
1373:
1352:
1349:
1322:
1319:
1316:
1312:
1289:
1285:
1263:
1260:
1239:
1234:
1231:
1228:
1224:
1220:
1217:
1214:
1211:
1208:
1203:
1199:
1195:
1190:
1186:
1182:
1161:
1158:
1135:
1132:
1129:
1125:
1121:
1118:
1115:
1112:
1109:
1104:
1100:
1096:
1091:
1087:
1064:
1061:
1058:
1054:
1031:
1027:
1004:
1000:
979:
974:
970:
966:
944:
940:
917:
913:
892:
872:
850:
846:
825:
803:
799:
778:
763:
756:
754:
751:
750:
749:
706:
695:
662:
659:
646:
642:
639:
636:
633:
630:
627:
624:
619:
615:
611:
606:
602:
580:
577:
574:
569:
565:
561:
556:
552:
530:
527:
524:
519:
515:
511:
508:
505:
502:
497:
493:
489:
484:
480:
443:
439:
418:
415:
394:
391:
350:
347:
345:)-colourable.
291:
288:
285:
280:
276:
240:
234:
216:. We consider
185:
182:
180:
177:
165:Dan Archdeacon
144:
124:
121:
118:
115:
112:
109:
89:
86:
83:
38:
35:
13:
10:
9:
6:
4:
3:
2:
2926:
2915:
2912:
2910:
2907:
2906:
2904:
2892:
2887:
2883:
2879:
2873:
2869:
2864:
2860:
2856:
2851:
2847:
2842:
2838:
2834:
2833:
2827:
2823:
2818:
2814:
2810:
2805:
2802:
2798:
2794:
2790:
2785:
2782:
2778:
2774:
2770:
2765:
2762:
2758:
2754:
2750:
2745:
2742:
2740:9780898713909
2736:
2732:
2728:
2723:
2719:
2714:
2710:
2706:
2701:
2697:
2692:
2688:
2684:
2679:
2675:
2670:
2666:
2662:
2657:
2656:
2651:
2642:
2640:9780898713909
2636:
2632:
2628:
2624:
2618:
2615:
2609:
2604:
2600:
2596:
2592:
2584:
2581:
2576:
2572:
2568:
2564:
2559:
2554:
2550:
2546:
2542:
2535:
2532:
2528:
2523:
2520:
2514:
2509:
2505:
2501:
2497:
2490:
2487:
2482:
2478:
2473:
2468:
2464:
2460:
2456:
2450:
2447:
2441:
2436:
2432:
2428:
2424:
2417:
2414:
2408:
2403:
2399:
2395:
2394:
2389:
2382:
2379:
2373:
2368:
2364:
2360:
2356:
2349:
2346:
2341:
2337:
2333:
2329:
2325:
2319:
2316:
2310:
2305:
2301:
2297:
2296:
2291:
2284:
2281:
2276:
2272:
2268:
2264:
2263:
2255:
2252:
2247:
2245:9780444894410
2241:
2237:
2233:
2229:
2222:
2219:
2214:
2210:
2206:
2202:
2198:
2192:
2190:
2188:
2186:
2184:
2182:
2180:
2178:
2174:
2167:
2165:
2158:
2156:
2142:
2122:
2110:
2108:
2107:-colourable.
2091:
2088:
2085:
2082:
2079:
2054:
2050:
2029:
2009:
1989:
1977:
1975:
1961:
1941:
1921:
1899:
1895:
1872:
1868:
1845:
1841:
1820:
1812:
1808:
1794:
1774:
1752:
1748:
1727:
1724:
1721:
1718:
1713:
1710:
1707:
1703:
1680:
1677:
1674:
1670:
1647:
1643:
1634:
1618:
1596:
1592:
1569:
1566:
1563:
1559:
1536:
1533:
1530:
1526:
1504:
1501:
1478:
1474:
1452:
1449:
1423:
1420:
1417:
1413:
1409:
1406:
1403:
1400:
1397:
1392:
1388:
1384:
1379:
1375:
1350:
1347:
1338:
1320:
1317:
1314:
1310:
1287:
1283:
1261:
1258:
1232:
1229:
1226:
1222:
1218:
1215:
1212:
1209:
1206:
1201:
1197:
1193:
1188:
1184:
1159:
1156:
1133:
1130:
1127:
1123:
1119:
1116:
1113:
1110:
1107:
1102:
1098:
1094:
1089:
1085:
1062:
1059:
1056:
1052:
1029:
1025:
1002:
998:
972:
968:
942:
938:
915:
911:
890:
870:
848:
844:
823:
801:
797:
776:
768:
761:
757:
752:
747:
743:
739:
735:
731:
727:
723:
719:
715:
711:
707:
704:
700:
696:
694:)-colourable.
693:
689:
685:
681:
677:
673:
669:
665:
664:
660:
658:
640:
637:
631:
628:
625:
617:
613:
604:
600:
591:
578:
575:
567:
563:
554:
550:
541:
528:
525:
517:
513:
506:
503:
495:
491:
482:
478:
469:
467:
463:
459:
441:
437:
423:
416:
414:
412:
408:
404:
400:
392:
390:
388:
384:
380:
376:
372:
368:
364:
360:
356:
348:
346:
344:
340:
336:
332:
328:
324:
320:
316:
312:
308:
303:
286:
278:
274:
265:
263:
258:
254:
250:
246:
238:
235:
233:
231:
227:
223:
219:
215:
211:
207:
203:
199:
195:
191:
183:
178:
176:
174:
170:
169:László Lovász
166:
162:
158:
142:
119:
113:
110:
107:
87:
84:
81:
73:
69:
65:
61:
57:
53:
49:
45:
36:
34:
32:
27:
23:
19:
2881:
2877:
2861:(1): 61–68,
2858:
2854:
2836:
2835:, Series B,
2830:
2815:(1): 91–94,
2812:
2808:
2795:(1): 73–75,
2792:
2788:
2772:
2768:
2752:
2748:
2730:
2708:
2704:
2686:
2682:
2664:
2660:
2630:
2623:Cowen, L. J.
2617:
2598:
2594:
2583:
2548:
2544:
2541:Oum, Sang-il
2534:
2527:Cowen, L. J.
2522:
2503:
2499:
2489:
2462:
2458:
2449:
2433:(1): 61–68.
2430:
2426:
2416:
2397:
2396:. Series B.
2391:
2381:
2365:(1): 95–96.
2362:
2358:
2348:
2331:
2327:
2318:
2302:(1): 91–94.
2299:
2293:
2283:
2269:(1): 73–75.
2266:
2260:
2254:
2227:
2221:
2204:
2200:
2197:Cowen, L. J.
2162:
2159:Applications
2114:
1981:
1810:
1809:
1632:
1335:. Hence, by
766:
765:
753:Some results
745:
741:
737:
733:
732:) such that
729:
725:
721:
717:
713:
709:
702:
691:
687:
683:
675:
671:
667:
592:
542:
470:
465:
461:
457:
428:
410:
406:
402:
398:
396:
386:
382:
378:
374:
370:
366:
362:
358:
354:
352:
342:
338:
334:
330:
326:
322:
318:
314:
310:
306:
304:
261:
260:
256:
252:
248:
244:
242:
236:
229:
225:
221:
217:
213:
209:
208:has at most
205:
201:
197:
193:
189:
187:
172:
160:
156:
67:
63:
59:
55:
51:
47:
43:
40:
25:
18:graph theory
15:
2733:: 548–557,
2633:: 548–557.
1337:contracting
385:is 0, then
2903:Categories
2652:References
1017:. Suppose
661:Properties
66:)- or (2,
2691:CiteSeerX
2689:: 21–32,
2669:CiteSeerX
2667:: 79–87,
2558:1407.5236
2467:CiteSeerX
2455:Cowen, L.
2083:−
2069:minor is
1725:⩾
1678:−
1518:contains
1429:⟩
1421:−
1410:∪
1398:∪
1385:∪
1372:⟨
1318:−
1238:⟩
1230:−
1219:∪
1207:∪
1194:∪
1181:⟨
1131:−
1120:∪
1108:∪
1095:∪
978:⟩
965:⟨
641:∈
635:∀
601:χ
551:χ
507:χ
479:χ
275:χ
224:= 0) and
85:≥
2575:12157191
2042:with no
1505:′
1453:′
1351:′
1262:′
1160:′
22:coloring
1493:. Thus
417:Example
192:,
155:is (4,
37:History
2737:
2693:
2671:
2637:
2573:
2469:
2242:
930:. Let
836:. Let
767:Proof:
758:Every
309:, the
2571:S2CID
2553:arXiv
2168:Notes
903:from
173:O(∆E)
2735:ISBN
2635:ISBN
2240:ISBN
1631:is (
769:Let
740:and
686:is (
670:is (
397:Let
353:Let
329:is (
251:is (
46:and
2886:doi
2863:doi
2841:doi
2817:doi
2797:doi
2777:doi
2757:doi
2713:doi
2709:126
2603:doi
2563:doi
2508:doi
2504:126
2477:doi
2435:doi
2402:doi
2367:doi
2336:doi
2304:doi
2271:doi
2232:doi
2209:doi
1695:or
1441:of
1250:of
957:be
682:of
365:of
313:of
188:A (
16:In
2905::
2882:21
2880:,
2859:21
2857:,
2837:23
2813:91
2811:,
2793:14
2791:,
2773:11
2771:,
2753:10
2751:,
2729:,
2707:,
2687:26
2685:,
2665:25
2663:,
2629:.
2599:21
2597:.
2593:.
2569:.
2561:.
2549:29
2547:.
2502:.
2498:.
2475:.
2463:24
2461:.
2431:21
2429:.
2425:.
2398:23
2390:.
2363:64
2361:.
2357:.
2332:11
2330:.
2300:91
2298:.
2292:.
2267:14
2265:.
2238:.
2205:10
2203:.
2176:^
1974:.
1807:.
744:≥
742:d′
736:≥
734:k′
730:d′
728:,
726:k′
722:d′
720:,
718:k′
712:,
690:,
674:,
302:.
266:,
255:,
54:,
33:)
2888::
2865::
2843::
2819::
2799::
2779::
2759::
2715::
2643:.
2611:.
2605::
2577:.
2565::
2555::
2516:.
2510::
2483:.
2479::
2443:.
2437::
2410:.
2404::
2375:.
2369::
2342:.
2338::
2312:.
2306::
2277:.
2273::
2248:.
2234::
2215:.
2211::
2143:G
2123:G
2095:)
2092:N
2089:,
2086:1
2080:t
2077:(
2055:t
2051:K
2030:G
2010:N
1990:t
1962:G
1942:i
1922:i
1900:i
1896:V
1873:i
1869:G
1846:i
1842:G
1821:G
1795:G
1775:i
1753:i
1749:V
1728:1
1722:i
1719:,
1714:1
1711:+
1708:i
1704:V
1681:1
1675:i
1671:V
1648:i
1644:V
1633:k
1619:G
1597:i
1593:G
1570:3
1567:,
1564:2
1560:K
1537:3
1534:,
1531:2
1527:K
1502:G
1479:i
1475:V
1450:G
1424:1
1418:i
1414:V
1407:.
1404:.
1401:.
1393:1
1389:V
1380:0
1376:V
1348:G
1321:1
1315:i
1311:V
1288:i
1284:V
1259:G
1233:1
1227:i
1223:V
1216:.
1213:.
1210:.
1202:1
1198:V
1189:0
1185:V
1157:G
1134:1
1128:i
1124:V
1117:.
1114:.
1111:.
1103:1
1099:V
1090:0
1086:V
1063:3
1060:,
1057:1
1053:K
1030:i
1026:G
1003:i
999:V
973:i
969:V
943:i
939:G
916:0
912:v
891:i
871:G
849:i
845:V
824:G
802:0
798:v
777:G
748:.
746:d
738:k
714:d
710:k
705:.
703:d
692:d
688:k
684:G
676:d
672:k
668:G
645:N
638:n
632:;
629:1
626:=
623:)
618:n
614:C
610:(
605:2
579:3
576:=
573:)
568:5
564:C
560:(
555:1
529:3
526:=
523:)
518:5
514:C
510:(
504:=
501:)
496:5
492:C
488:(
483:0
466:k
462:k
458:k
442:5
438:C
411:G
407:c
403:G
399:c
387:v
383:v
379:v
375:v
371:c
367:G
363:v
359:G
355:c
343:d
339:d
335:d
333:,
331:k
327:G
323:d
319:k
315:G
307:G
290:)
287:G
284:(
279:d
262:d
257:d
253:k
249:G
245:k
237:d
230:k
226:d
222:k
218:k
214:v
210:d
206:v
202:k
198:G
194:d
190:k
161:k
157:k
143:g
123:)
120:g
117:(
114:k
111:=
108:k
88:0
82:g
68:d
64:d
60:d
56:d
52:k
48:d
44:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
