### 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(H^{2}) = χ(H^{2}) 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 H^{2} or T(C) is (a : b)-choosable, then it is (ta : tb)-choosable for every positive integer t.

Original language | English (US) |
---|---|

Pages (from-to) | 123-143 |

Number of pages | 21 |

Journal | Discrete Mathematics |

Volume | 240 |

Issue number | 1-3 |

DOIs | |

State | Published - 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

*Discrete Mathematics*,

*240*(1-3), 123-143. https://doi.org/10.1016/S0012-365X(00)00371-X