首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Choosability conjectures and multicircuits
Authors:Alexandr V Kostochka and Douglas R Woodall
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.
Keywords:Graph colouring  List-colouring conjecture  List-edge-colouring conjecture  List-total-colouring conjecture  List-square-colouring conjecture  Choosability conjectures  Total choosability  List chromatic number  List total chromatic number  Inflation of a graph  Square of a graph  Multicircuit
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号