Bridgeless Cubic Graphs Are (7,2)-Edge-Choosable
Edita Máčajová · SIAM Journal on Discrete Mathematics · 2013
A graph $G$ is called $(r,s)$-edge-choosable if for every assignment of sets of size $r$ to the edges of $G$ it is possible to choose for every edge an $s$-element subset from its set such that the subsets chosen for any pair of adjacent edges are disjoint. The list fractional chromatic index of a graph $G$ is the infimum of all numbers $r/s$ for which $G$ is $(r,s)$-edge-choosable. Mohar [http://www.fmf.uni-lj.si/$\sim$mohar/ (June 2003)] posed a problem asking whether every cubic graph is (7,2)-edge-choosable. In 2009, Cranston and West [SIAM J. Discrete Math., 23 (2009), pp. 872--881] showed that every 3-edge-colorable cubic graph is (7,2)-edge-choosable and gave a sufficient condition with the help of which they proved that many non-3-edge-colorable cubic graphs are (7,2)-edge-choosable. In this paper we prove that every bridgeless cubic graph is (7,2)-edge-choosable. We show that this result cannot be improved in the family of all cubic graphs, in the sense that there exists a cubic graph with list fractional chromatic index $7/2$. The original question of Mohar remains open, and we further pose several related problems.