Institution: | a Institute of Mathematics, Novosibirsk, 630090, Russia b Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA c School of Mathematical Sciences, University of Nottingham, University Park, Nottingham, NG7 2RD, UK |
Abstract: | 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. |