Choosability conjectures and multicircuits

Alexandr V. Kostochka, Douglas R. Woodal

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)123-143
Number of pages21
JournalDiscrete Mathematics
Volume240
Issue number1-3
DOIs
StatePublished - Sep 28 2001

Keywords

  • Choosability conjectures
  • Graph colouring
  • List chromatic number
  • List-colouring conjecture
  • List-edge-colouring conjecture
  • List-square-colouring conjecture
  • List-total- colouring conjecture
  • Total choosability

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Choosability conjectures and multicircuits'. Together they form a unique fingerprint.

  • Cite this