PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2015 | 35 | 1 | 197-202
Tytuł artykułu

Fractional Aspects of the Erdős-Faber-Lovász Conjecture

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
35
Numer
1
Strony
197-202
Opis fizyczny
Daty
wydano
2015-02-01
otrzymano
2013-05-22
poprawiono
2013-11-28
zaakceptowano
2014-02-20
online
2015-02-06
Twórcy
autor
  • Department of Mathematics and Computer Science Royal Military College of Canada PO Box 17000 Stn Forces, Kingston, ON Canada, K7K 7B4, John.Bosica@rmc.ca
  • Department of Mathematics and Computer Science Royal Military College of Canada PO Box 17000 Stn Forces, Kingston, ON Canada, K7K 7B4, Claude.Tardif@rmc.ca
Bibliografia
  • [1] N.G. de Bruijn and P. Erdős, On a combinatorial problem, Nederl. Akad. Wetensch.
  • 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]
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1781
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.