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

DOI10.19086/AIC.10811zbMATH Open1450.05074arXiv1806.03880OpenAlexW2807314195MaRDI QIDQ5126751FDOQ5126751

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

Publication date: 20 October 2020

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

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.

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

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

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)

Cited In (6)

• A note on fractional DP-coloring of graphs
• The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Multiple list coloring of 3‐choice critical graphs
• The strong fractional choice number of series-parallel 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)