Fractional list and correspondence packing conjectures

About 3 years old · traced to

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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.