Back to Search
Start Over
BRIDGELESS CUBIC GRAPHS ARE (7,2)-EDGE-CHOOSABLE.
- Source :
-
SIAM Journal on Discrete Mathematics . 2013, Vol. 27 Issue 2, p757-767. 11p. - Publication Year :
- 2013
-
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]
- Subjects :
- *GRAPH theory
*SUBSET selection
*SET theory
*MATHEMATICS
*GRAPHIC methods
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 27
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 89041338
- Full Text :
- https://doi.org/10.1137/110840820