Fractional list and correspondence packing conjectures

From papers

Let GG be a graph. Write χ(G)\chi_\ell^\bullet(G) and χc(G)\chi_c^\bullet(G) for its fractional list and fractional correspondence packing numbers, and write χ(G)\chi_\ell(G) and χc(G)\chi_c(G) for the corresponding ordinary list and correspondence chromatic numbers.

Fractional packing conjectures. There exists a constant C>0C>0 such that, for every graph GG,

χ(G)Cχ(G),\chi_\ell^\bullet(G)\leq C\cdot\chi_\ell(G),

and there exists a constant C>0C>0 such that, for every graph GG,

χc(G)Cχc(G).\chi_c^\bullet(G)\leq C\cdot\chi_c(G).

The fractional parameters provide relaxations of the integral packing numbers, and the paper proves an upper bound in terms of maximum degree for the fractional versions. Whether each fractional parameter is bounded by a universal constant multiple of its integral counterpart remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Stijn Cambie, Wouter Cames van Batenburg, Ewan Davies and Ross J. Kang, “List packing number of bounded degree graphs”, arXiv:2303.01246 (2023).

Solutions 0

No solutions have been posted yet.