TY - JOUR
T1 - Choosability conjectures and multicircuits
AU - Kostochka, Alexandr V.
AU - Woodal, Douglas R.
N1 - Funding Information:
∗Corresponding author. Tel.: +44-115-951-4959; fax: +44-115-951-4951. E-mail address: [email protected] (D.R. Woodall). 1Part of this work was carried out while the Frst author was visiting Nottingham, funded by Visiting Fellowship Research Grant GR=L54585 from the Engineering and Physical Sciences Research Council. The work of this author was also partly supported by grants 96-01-01614 and 97-01-01075 of the Russian Foundation for Fundamental Research.
PY - 2001/9/28
Y1 - 2001/9/28
N2 - This paper starts with a discussion of several old and new conjectures about choosability in graphs. In particular, the list-colouring conjecture, that ch′ = χ′ for every multigraph, is shown to imply that if a line graph is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t. It is proved that ch(H2) = χ(H2) for many "small" graphs H, including inflations of all circuits (connected 2-regular graphs) with length at most 11 except possibly length 9; and that ch″(C) = χ″(C) (the total chromatic number) for various multicircuits C, mainly of even order, where a multicircuit is a multigraph whose underlying simple graph is a circuit. In consequence, it is shown that if any of the corresponding graphs H2 or T(C) is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t.
AB - This paper starts with a discussion of several old and new conjectures about choosability in graphs. In particular, the list-colouring conjecture, that ch′ = χ′ for every multigraph, is shown to imply that if a line graph is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t. It is proved that ch(H2) = χ(H2) for many "small" graphs H, including inflations of all circuits (connected 2-regular graphs) with length at most 11 except possibly length 9; and that ch″(C) = χ″(C) (the total chromatic number) for various multicircuits C, mainly of even order, where a multicircuit is a multigraph whose underlying simple graph is a circuit. In consequence, it is shown that if any of the corresponding graphs H2 or T(C) is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t.
KW - Choosability conjectures
KW - Graph colouring
KW - List chromatic number
KW - List-colouring conjecture
KW - List-edge-colouring conjecture
KW - List-square-colouring conjecture
KW - List-total- colouring conjecture
KW - Total choosability
UR - http://www.scopus.com/inward/record.url?scp=0035964589&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035964589&partnerID=8YFLogxK
U2 - 10.1016/S0012-365X(00)00371-X
DO - 10.1016/S0012-365X(00)00371-X
M3 - Article
AN - SCOPUS:0035964589
SN - 0012-365X
VL - 240
SP - 123
EP - 143
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -