388:
534:: no matter what set of colors is chosen for the vertices on the small side of the bipartition, this choice will conflict with all of the colors for one of the vertices on the other side of the bipartition. For instance if the vertex with color set {00,01} is colored 01, and the vertex with color set {10,11} is colored 10, then the vertex with color set {01,10} cannot be colored. Therefore, the list chromatic number of
356:
the lists {red, blue} and {green, black}. Assign to the other four vertices the lists {red, green}, {red, black}, {blue, green}, and {blue, black}. No matter which choice one makes of a color from the list of
401:
with three colors per vertex. No matter which colors are chosen for the three central vertices, one of the outer 27 vertices will be uncolorable, showing that the list chromatic number of
921:
599:
961:
232:
642:
are used on the other, there must be one color which is used on both sides, but this implies that two adjacent vertices have the same color. In particular, the
1428:
1006:
of the graph, after which no more such deletions are possible. The initial graph is 2-choosable if and only if its 2-core is either an even cycle or a
1484:
Garg, N.; Papatriantafilou, M.; Tsigas, P. (1996), "Distributed list coloring: how to dynamically allocate frequencies to mobile base stations",
622: − 1 colors are available in total, and that, on a single side of the bipartition, each vertex has available to it a different
1547:
1511:
1460:
1251:
1055:
980:
1194:
1158:
1386:
1331:
1075:
32:
where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by
1125:
1010:
formed by three paths with shared endpoints, with two paths of length two and the third path having any even length.
1569:
384:
leaves at least one available color for each of the remaining vertices, and these colors may be chosen arbitrarily.
1003:
992:
365:, there will be some other vertex such that both of its choices are already used to color its neighbors. Thus,
684:
421:
392:
711:-list-colorable graph must in particular have a list coloring when every vertex is assigned the same list of
1584:
876:
1443:
Wang, Wei; Liu, Xin (2005), "List-coloring based channel allocation for open-spectrum wireless networks",
1294:
548:
1299:
626:-tuple of these colors than each other vertex. Then, each side of the bipartition must use at least
968:
934:
1517:
1466:
1358:
1340:
1312:
1027:
1543:
1507:
1456:
1051:
1497:
1489:
1448:
1395:
1350:
1304:
1263:
1084:
746:. In particular, as the complete bipartite graph examples show, there exist graphs with χ(
202:
1098:
726:) cannot be bounded in terms of chromatic number in general, that is, there is no function
1412:
1229:
1094:
972:
815:
255:
97:
33:
634: − 1 colors will be disjoint from the list of one vertex. Since at least
967:≥ 3, and the same applies for 4-choosability in planar graphs, 3-choosability in planar
348:
has list-chromatic number larger than 2, as the following construction shows: assign to
676:
29:
1432:, Lecture Notes on Computer Science, vol. 5734, Springer-Verlag, pp. 382–391
344:
in another and no two adjacent vertices will have the same color. On the other hand,
1578:
1502:
1354:
1117:
1089:
643:
37:
1470:
1316:
1205:
1169:
1018:
List coloring arises in practical problems concerning channel/frequency assignment.
387:
1521:
1362:
1121:
800:
41:
17:
1452:
1127:
Proc. West Coast
Conference on Combinatorics, Graph Theory and Computing, Arcata
1007:
999:
21:
1416:
1399:
1134:
984:
1493:
1282:
1268:
1002:
by repeatedly deleting vertices of degree zero or one until reaching the
1133:, Congressus Numerantium, vol. 26, pp. 125–157, archived from
1308:
519:
The illustration shows a larger example of the same construction, with
114:) if it has a proper list coloring no matter how one assigns a list of
92:). As with graph coloring, a list coloring is generally assumed to be
467:} in which the first digits are equal to each other, for each of the
1329:
Gutner, Shai (1996), "The complexity of planar graph choosability",
1073:
Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring",
1345:
441:
1285:; Tarsi, Michael (1992), "Colorings and orientations of graphs",
835:
Two algorithmic problems have been considered in the literature:
187:) if it has a list coloring no matter how one assigns a list of
1445:
2005 IEEE 62nd
Vehicular Technology Conference (VTC 2005-Fall)
495:} in which the first digits are all distinct, for each of the
316:, and no other vertices are connected. As a bipartite graph,
1486:
Eighth IEEE Symposium on
Parallel and Distributed Processing
1046:
Jensen, Tommy R.; Toft, Bjarne (1995), "1.9 List coloring",
376:
is 3-choosable: picking arbitrary colors for the vertices
998:
It is possible to test whether a graph is 2-choosable in
652:
has list-chromatic number at least three, and the graph
1376:
Gutner, Shai; Tarsi, Michael (2009), "Some results on (
937:
879:
551:
205:
1542:(4th ed.), Berlin, New York: Springer-Verlag,
1195:"On two short proofs about list coloring - Part 2"
1159:"On two short proofs about list coloring - Part 1"
955:
915:
593:
226:
585:
561:
436:. Let the available colors be represented by the
1050:, New York: Wiley-Interscience, pp. 18–21,
475:. On the other side of the bipartition, let the
1124:; Taylor, H. (1979), "Choosability in graphs",
1232:(1976), "Vertex colorings with given colors",
1254:(1994), "Every planar graph is 5-choosable",
8:
1429:Mathematical Foundations of Computer Science
910:
892:
320:has usual chromatic number 2: one may color
1564:. 3rd edition, Springer, 2005. Chapter 5.4
447:. On one side of the bipartition, let the
372:On the other hand, it is easy to see that
1570:electronic edition available for download
1501:
1344:
1298:
1267:
1256:Journal of Combinatorial Theory, Series B
1088:
947:
942:
936:
878:
659:has list-chromatic number at least four.
638:colors are used on one side and at least
584:
560:
558:
550:
471:possible choices of the first digit
204:
1538:Aigner, Martin; Ziegler, Günter (2009),
386:
1112:
1110:
1108:
1038:
695:) satisfies the following properties.
1068:
1066:
931:-choosability in bipartite graphs is
916:{\displaystyle f:V\to \{a,\dots ,b\}}
715:colors, which corresponds to a usual
7:
601:, then the complete bipartite graph
594:{\displaystyle n={\binom {2k-1}{k}}}
100:receive the same color. A graph is
939:
869:: decide whether a given graph is
846:: decide whether a given graph is
565:
530:does not have a list coloring for
14:
1447:, vol. 1, pp. 690–694,
479:vertices be given sets of colors
451:vertices be given sets of colors
873:-choosable for a given function
391:A list coloring instance on the
691:. The list coloring number ch(
618:-choosable. For, suppose that 2
440:different two-digit numbers in
416:be a positive integer, and let
153:More generally, for a function
979:-free graphs, that is, graphs
889:
215:
209:
1:
971:, and (2, 3)-choosability in
773:is the number of vertices of
630:colors, because every set of
361:and a color from the list of
300:are each connected to all of
242:-choosability corresponds to
157:assigning a positive integer
1355:10.1016/0012-365X(95)00104-5
1090:10.1016/0012-365X(95)00350-6
956:{\displaystyle \Pi _{2}^{p}}
823:Computing choosability and (
750:) = 2 but with ch(
118:colors to each vertex. The
64:) of colors for each vertex
1453:10.1109/VETECF.2005.1558001
1601:
1555:Five-coloring plane graphs
1400:10.1016/j.disc.2008.04.061
1503:21.11116/0000-0001-1AE6-F
1415:; Golovach, Petr (2009),
993:fixed-parameter tractable
742:)) holds for every graph
1494:10.1109/SPDP.1996.570312
499:possible choices of the
422:complete bipartite graph
393:complete bipartite graph
195:) colors to each vertex
1234:Metody Diskret. Analiz.
1048:Graph coloring problems
850:-choosable for a given
84:to a color in the list
80:that maps every vertex
1269:10.1006/jctb.1994.1062
957:
917:
595:
409:
268:, having six vertices
254:Consider the complete
228:
227:{\displaystyle f(v)=k}
1193:Eaton, Nancy (2003),
1157:Eaton, Nancy (2003),
958:
918:
596:
390:
229:
199:. In particular, if
128:list chromatic number
1540:Proofs from THE BOOK
1387:Discrete Mathematics
1332:Discrete Mathematics
1076:Discrete Mathematics
975:planar graphs. For P
969:triangle-free graphs
935:
877:
754:) arbitrarily large.
549:
412:More generally, let
369:is not 2-choosable.
203:
138:is the least number
1560:Diestel, Reinhard.
952:
1488:, pp. 18–25,
1417:"Choosability of P
1309:10.1007/BF01204715
1252:Thomassen, Carsten
1211:on August 30, 2017
1175:on August 29, 2017
1028:List edge-coloring
963:-complete for any
953:
938:
913:
591:
410:
224:
1549:978-3-642-00855-9
1384:)-choosability",
991:-choosability is
927:It is known that
583:
408:is at least four.
328:in one color and
234:for all vertices
165:) to each vertex
124:list colorability
98:adjacent vertices
96:, meaning no two
1592:
1552:
1526:
1524:
1505:
1481:
1475:
1473:
1440:
1434:
1433:
1425:
1413:Heggernes, Pinar
1409:
1403:
1402:
1394:(8): 2260–2270,
1373:
1367:
1365:
1348:
1326:
1320:
1319:
1302:
1279:
1273:
1272:
1271:
1248:
1242:
1241:
1226:
1220:
1219:
1218:
1216:
1210:
1204:, archived from
1199:
1190:
1184:
1183:
1182:
1180:
1174:
1168:, archived from
1163:
1154:
1148:
1147:
1146:
1145:
1139:
1132:
1114:
1103:
1101:
1092:
1083:(1–3): 299–302,
1070:
1061:
1060:
1043:
962:
960:
959:
954:
951:
946:
922:
920:
919:
914:
677:chromatic number
600:
598:
597:
592:
590:
589:
588:
579:
564:
542: + 1.
523: = 3.
518:
494:
466:
233:
231:
230:
225:
56:and given a set
1600:
1599:
1595:
1594:
1593:
1591:
1590:
1589:
1575:
1574:
1550:
1537:
1532:Further reading
1529:
1514:
1483:
1482:
1478:
1463:
1442:
1441:
1437:
1423:
1420:
1411:
1410:
1406:
1375:
1374:
1370:
1328:
1327:
1323:
1300:10.1.1.106.9928
1281:
1280:
1276:
1250:
1249:
1245:
1228:
1227:
1223:
1214:
1212:
1208:
1197:
1192:
1191:
1187:
1178:
1176:
1172:
1161:
1156:
1155:
1151:
1143:
1141:
1137:
1130:
1116:
1115:
1106:
1072:
1071:
1064:
1058:
1045:
1044:
1040:
1036:
1024:
1016:
978:
933:
932:
875:
874:
833:
665:
658:
651:
613:
566:
559:
547:
546:
504:
480:
452:
435:
407:
400:
267:
256:bipartite graph
252:
246:-choosability.
201:
200:
185:-list-colorable
112:-list-colorable
78:choice function
50:
12:
11:
5:
1598:
1596:
1588:
1587:
1585:Graph coloring
1577:
1576:
1573:
1572:
1566:List Colouring
1558:
1548:
1528:
1527:
1512:
1476:
1461:
1435:
1418:
1404:
1368:
1339:(1): 119–130,
1321:
1293:(2): 125–134,
1274:
1243:
1236:(in Russian),
1221:
1185:
1149:
1104:
1062:
1056:
1037:
1035:
1032:
1031:
1030:
1023:
1020:
1015:
1012:
976:
950:
945:
941:
925:
924:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
882:
855:
832:
831:)-choosability
821:
820:
819:
804:
789:
778:
755:
720:
685:maximum degree
664:
661:
656:
649:
605:
587:
582:
578:
575:
572:
569:
563:
557:
554:
545:Similarly, if
427:
405:
398:
265:
251:
248:
223:
220:
217:
214:
211:
208:
52:Given a graph
49:
46:
44:, and Taylor.
30:graph coloring
20:, a branch of
13:
10:
9:
6:
4:
3:
2:
1597:
1586:
1583:
1582:
1580:
1571:
1567:
1563:
1559:
1556:
1553:, Chapter 34
1551:
1545:
1541:
1536:
1535:
1534:
1533:
1523:
1519:
1515:
1513:0-8186-7683-3
1509:
1504:
1499:
1495:
1491:
1487:
1480:
1477:
1472:
1468:
1464:
1462:0-7803-9152-7
1458:
1454:
1450:
1446:
1439:
1436:
1431:
1430:
1422:
1421:-free graphs"
1414:
1408:
1405:
1401:
1397:
1393:
1389:
1388:
1383:
1379:
1372:
1369:
1364:
1360:
1356:
1352:
1347:
1342:
1338:
1334:
1333:
1325:
1322:
1318:
1314:
1310:
1306:
1301:
1296:
1292:
1288:
1287:Combinatorica
1284:
1278:
1275:
1270:
1265:
1261:
1257:
1253:
1247:
1244:
1239:
1235:
1231:
1230:Vizing, V. G.
1225:
1222:
1207:
1203:
1196:
1189:
1186:
1171:
1167:
1160:
1153:
1150:
1140:on 2016-03-09
1136:
1129:
1128:
1123:
1119:
1113:
1111:
1109:
1105:
1100:
1096:
1091:
1086:
1082:
1078:
1077:
1069:
1067:
1063:
1059:
1057:0-471-02865-7
1053:
1049:
1042:
1039:
1033:
1029:
1026:
1025:
1021:
1019:
1013:
1011:
1009:
1005:
1001:
996:
994:
990:
986:
982:
974:
970:
966:
948:
943:
930:
907:
904:
901:
898:
895:
886:
883:
880:
872:
868:
864:
860:
856:
853:
849:
845:
841:
838:
837:
836:
830:
826:
822:
818:planar graph.
817:
813:
809:
805:
802:
798:
794:
790:
787:
783:
779:
776:
772:
768:
764:
760:
756:
753:
749:
745:
741:
737:
733:
730:such that ch(
729:
725:
721:
718:
714:
710:
706:
702:
698:
697:
696:
694:
690:
686:
682:
678:
675:) denote the
674:
670:
662:
660:
655:
648:
645:
644:utility graph
641:
637:
633:
629:
625:
621:
617:
612:
608:
604:
580:
576:
573:
570:
567:
555:
552:
543:
541:
537:
533:
529:
524:
522:
516:
512:
508:
502:
498:
492:
488:
484:
478:
474:
470:
464:
460:
456:
450:
446:
443:
439:
434:
430:
426:
423:
419:
415:
404:
397:
394:
389:
385:
383:
379:
375:
370:
368:
364:
360:
355:
351:
347:
343:
339:
335:
331:
327:
323:
319:
315:
311:
307:
303:
299:
295:
291:
287:
283:
279:
275:
271:
264:
260:
257:
249:
247:
245:
241:
237:
221:
218:
212:
206:
198:
194:
190:
186:
184:
179:
177:
172:
168:
164:
160:
156:
151:
149:
145:
141:
137:
134:) of a graph
133:
129:
125:
121:
117:
113:
111:
106:
104:
99:
95:
91:
87:
83:
79:
75:
74:list coloring
71:
67:
63:
59:
55:
47:
45:
43:
39:
35:
31:
28:is a type of
27:
26:list coloring
23:
19:
1565:
1562:Graph Theory
1561:
1554:
1539:
1531:
1530:
1485:
1479:
1444:
1438:
1427:
1407:
1391:
1385:
1381:
1377:
1371:
1336:
1330:
1324:
1290:
1286:
1277:
1259:
1255:
1246:
1237:
1233:
1224:
1213:, retrieved
1206:the original
1201:
1188:
1177:, retrieved
1170:the original
1165:
1152:
1142:, retrieved
1135:the original
1126:
1122:Rubin, A. L.
1080:
1074:
1047:
1041:
1017:
1014:Applications
997:
988:
964:
928:
926:
870:
867:choosability
866:
862:
858:
851:
847:
844:choosability
843:
839:
834:
828:
824:
811:
807:
801:planar graph
796:
792:
785:
781:
774:
770:
766:
762:
758:
751:
747:
743:
739:
735:
731:
727:
723:
716:
712:
708:
704:
700:
692:
688:
680:
672:
668:
667:For a graph
666:
653:
646:
639:
635:
631:
627:
623:
619:
615:
610:
606:
602:
544:
539:
538:is at least
535:
531:
527:
525:
520:
514:
510:
506:
500:
496:
490:
486:
482:
476:
472:
468:
462:
458:
454:
448:
444:
437:
432:
428:
424:
417:
413:
411:
402:
395:
381:
377:
373:
371:
366:
362:
358:
353:
349:
345:
341:
337:
333:
329:
325:
321:
317:
313:
309:
305:
301:
297:
293:
289:
285:
281:
277:
273:
269:
262:
258:
253:
243:
239:
235:
196:
192:
188:
182:
181:
175:
174:
170:
166:
162:
158:
154:
152:
150:-choosable.
147:
143:
139:
135:
131:
127:
123:
120:choosability
119:
115:
109:
108:
102:
101:
93:
89:
85:
81:
77:
73:
69:
65:
61:
57:
53:
51:
25:
18:graph theory
15:
1262:: 180–181,
1008:theta graph
1000:linear time
983:a 5-vertex
22:mathematics
1283:Alon, Noga
1144:2008-11-10
1034:References
985:path graph
719:-coloring.
663:Properties
292:such that
178:-choosable
169:, a graph
142:such that
105:-choosable
68:(called a
48:Definition
1346:0802.2668
1295:CiteSeerX
1118:Erdős, P.
981:excluding
973:bipartite
940:Π
902:…
890:→
816:bipartite
810:) ≤ 3 if
795:) ≤ 5 if
574:−
1579:Category
1471:14952297
1317:45528500
1022:See also
769:) where
671:, let χ(
250:Examples
1522:3319306
1363:1392057
1215:May 29,
1179:May 29,
1099:1388650
614:is not
517:, ...).
503:-tuple
420:be the
36:and by
1546:
1520:
1510:
1469:
1459:
1361:
1315:
1297:
1240:: 3–10
1097:
1054:
1004:2-core
788:) + 1.
784:) ≤ Δ(
761:) ≤ χ(
707:). A
703:) ≥ χ(
683:) the
679:and Δ(
526:Then,
465:2, ...
312:, and
94:proper
34:Vizing
1518:S2CID
1467:S2CID
1424:(PDF)
1359:S2CID
1341:arXiv
1313:S2CID
1209:(PDF)
1198:(PDF)
1173:(PDF)
1162:(PDF)
1138:(PDF)
1131:(PDF)
854:, and
814:is a
799:is a
765:) ln(
657:10,10
493:, ...
442:radix
130:) ch(
76:is a
72:), a
42:Rubin
38:Erdős
1544:ISBN
1508:ISBN
1457:ISBN
1217:2010
1202:Talk
1181:2010
1166:Talk
1052:ISBN
734:) ≤
406:3,27
399:3,27
380:and
352:and
324:and
296:and
180:(or
122:(or
107:(or
70:list
1498:hdl
1490:doi
1449:doi
1396:doi
1392:309
1351:doi
1337:159
1305:doi
1264:doi
1085:doi
1081:152
806:ch(
791:ch(
780:ch(
757:ch(
738:(χ(
722:ch(
699:ch(
687:of
650:3,3
489:, 2
485:, 1
461:1,
457:0,
266:2,4
173:is
146:is
126:or
16:In
1581::
1568:.
1516:,
1506:,
1496:,
1465:,
1455:,
1426:,
1390:,
1357:,
1349:,
1335:,
1311:,
1303:,
1291:12
1289:,
1260:62
1258:,
1238:29
1200:,
1164:,
1120:;
1107:^
1095:MR
1093:,
1079:,
1065:^
995:.
987:,
865:)-
861:,
827:,
609:,
513:,
509:,
481:{0
340:,
336:,
332:,
308:,
304:,
288:,
284:,
280:,
276:,
272:,
261:=
238:,
40:,
24:,
1557:.
1525:.
1500::
1492::
1474:.
1451::
1419:5
1398::
1382:b
1380::
1378:a
1366:.
1353::
1343::
1307::
1266::
1102:.
1087::
989:k
977:5
965:k
949:p
944:2
929:k
923:.
911:}
908:b
905:,
899:,
896:a
893:{
887:V
884::
881:f
871:f
863:b
859:a
857:(
852:k
848:k
842:-
840:k
829:b
825:a
812:G
808:G
803:.
797:G
793:G
786:G
782:G
777:.
775:G
771:n
767:n
763:G
759:G
752:G
748:G
744:G
740:G
736:f
732:G
728:f
724:G
717:k
713:k
709:k
705:G
701:G
693:G
689:G
681:G
673:G
669:G
654:K
647:K
640:k
636:k
632:k
628:k
624:k
620:k
616:k
611:n
607:n
603:K
586:)
581:k
577:1
571:k
568:2
562:(
556:=
553:n
540:q
536:G
532:L
528:G
521:q
515:c
511:b
507:a
505:(
501:q
497:q
491:c
487:b
483:a
477:q
473:i
469:q
463:i
459:i
455:i
453:{
449:q
445:q
438:q
433:q
431:,
429:q
425:K
418:G
414:q
403:K
396:K
382:B
378:A
374:G
367:G
363:B
359:A
354:B
350:A
346:G
342:Z
338:Y
334:X
330:W
326:B
322:A
318:G
314:Z
310:Y
306:X
302:W
298:B
294:A
290:Z
286:Y
282:X
278:W
274:B
270:A
263:K
259:G
244:k
240:f
236:v
222:k
219:=
216:)
213:v
210:(
207:f
197:v
193:v
191:(
189:f
183:f
176:f
171:G
167:v
163:v
161:(
159:f
155:f
148:k
144:G
140:k
136:G
132:G
116:k
110:k
103:k
90:v
88:(
86:L
82:v
66:v
62:v
60:(
58:L
54:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
