1. BRIDGELESS CUBIC GRAPHS ARE (7,2)-EDGE-CHOOSABLE.
- Author
-
MÁČAJOVÁ, EDITA
- Subjects
GRAPH theory ,SUBSET selection ,SET theory ,MATHEMATICS ,GRAPHIC methods - Abstract
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/~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. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF