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: douglas.woodall@nottingham.ac.uk (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

VL - 240

SP - 123

EP - 143

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -