Fractional Aspects of the Erdős-Faber-Lovász Conjecture
Discussiones Mathematicae Graph Theory (2015)
- Volume: 35, Issue: 1, page 197-202
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topJohn Bosica, and Claude Tardif. "Fractional Aspects of the Erdős-Faber-Lovász Conjecture." Discussiones Mathematicae Graph Theory 35.1 (2015): 197-202. <http://eudml.org/doc/271234>.
@article{JohnBosica2015,
abstract = {The Erdős-Faber-Lovász conjecture is the statement that every graph that is the union of n cliques of size n intersecting pairwise in at most one vertex has chromatic number n. Kahn and Seymour proved a fractional version of this conjecture, where the chromatic number is replaced by the fractional chromatic number. In this note we investigate similar fractional relaxations of the Erdős-Faber-Lovász conjecture, involving variations of the fractional chromatic number. We exhibit some relaxations that can be proved in the spirit of the Kahn-Seymour result, and others that are equivalent to the original conjecture.},
author = {John Bosica, Claude Tardif},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Erdős-Faber-Lovász Conjecture; fractional chromatic number; Erdős-Faber-Lovász conjecture},
language = {eng},
number = {1},
pages = {197-202},
title = {Fractional Aspects of the Erdős-Faber-Lovász Conjecture},
url = {http://eudml.org/doc/271234},
volume = {35},
year = {2015},
}
TY - JOUR
AU - John Bosica
AU - Claude Tardif
TI - Fractional Aspects of the Erdős-Faber-Lovász Conjecture
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 1
SP - 197
EP - 202
AB - The Erdős-Faber-Lovász conjecture is the statement that every graph that is the union of n cliques of size n intersecting pairwise in at most one vertex has chromatic number n. Kahn and Seymour proved a fractional version of this conjecture, where the chromatic number is replaced by the fractional chromatic number. In this note we investigate similar fractional relaxations of the Erdős-Faber-Lovász conjecture, involving variations of the fractional chromatic number. We exhibit some relaxations that can be proved in the spirit of the Kahn-Seymour result, and others that are equivalent to the original conjecture.
LA - eng
KW - Erdős-Faber-Lovász Conjecture; fractional chromatic number; Erdős-Faber-Lovász conjecture
UR - http://eudml.org/doc/271234
ER -
References
top- [1] N.G. de Bruijn and P. Erdős, On a combinatorial problem, Nederl. Akad. Wetensch. Zbl0032.24405
- Indag. Math 10 (1948) 421-423.
- [2] P. Erdős, R.C. Mullin, V.T. Sos and D.R. Stinson, Finite linear spaces and projective planes, Discrete Math. 47 (1983) 49-62. doi:10.1016/0012-365X(83)90071-7[Crossref] Zbl0521.51005
- [3] J. Kahn, Coloring nearly-disjoint hypergraphs with n+o(n) colors, J. Combin. The- ory (A) 59 (1992) 31-39. doi:10.1016/0097-3165(92)90096-D[Crossref]
- [4] J. Kahn and P.D. Seymour, A fractional version of the Erdős-Faber-Lovász conjec- ture, Combinatorica 12 (1992) 155-160. doi:10.1007/BF01204719[Crossref]
- [5] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1997).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.