Problem 632

A graph is $(a,b)$ -choosable if for any assignment of a list of $a$ colours to each of its vertices there is a subset of $b$ colours from each list such that the subsets of adjacent vertices are disjoint.

If $G$ is $(a,b)$ -choosable then $G$ is $(am,bm)$ -choosable for every integer $m\geq 1$ .

Source: erdosproblems.com/632

Graph theory
Chromatic number

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. Being $(a,1)$ -choosable is the same as being $a$ -choosable, that is, having list chromatic number at most $a$ . Dvořák, Hu and Sereni [DHS19] constructed a graph that is $4$ -choosable but not $(8,2)$ -choosable, a counterexample to the conjectured implication at $m=2$ ; the result is the accepted full claim Dvořák, Hu and Sereni. The question is from Erdős, Rubin and Taylor [ERT80], who printed it as an open question; a positive answer is sometimes called the $(am,bm)$ -conjecture.

Problem 632

Status

Proof claims

Discussion