A 4-choosable graph that is not (8:2)-choosable

DOI10.19086/AIC.10811MaRDI QIDQ5126751zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Xiaolan Hu, Jean-Sébastien Sereni

Publication date 20 October 2020

Published in Advances in Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1806.03880

zbMATH Keywords

list coloring\((a:b)\)-choosable graph\((am:bm)\)-conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: In 1980, ErdH{o}s, Rubin and Taylor asked whether for all positive integers $a$, $b$, and $m$, every $(a:b)$-choosable graph is also $(am:bm)$-choosable. We provide a negative answer by exhibiting a $4$-choosable graph that is not $(8:2)$-choosable.

Recommendations

• Some results on (a:b)-choosability
• On \((4,2)\)-choosable graphs
• A characterization of \((4,2)\)-choosable graphs
• \((4m,m)\)-choosability of plane graphs
• scientific article; zbMATH DE number 908794

Cited in

(8)

• A note on fractional DP-coloring of graphs
• The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs
• Indicated multifold-choosability of graphs
• Some results on (a:b)-choosability
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• The strong fractional choice number of series-parallel graphs
• Multiple list coloring of 3‐choice critical graphs
• Multiple list colouring triangle free planar graphs

This page was built for publication: A 4-choosable graph that is not \((8:2)\)-choosable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5126751)