A clone-theoretic formulation of the Erdos-Faber-Lovász conjecture

Lucien Haddad; Claude Tardif

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 3, page 545-549
  • ISSN: 2083-5892

Abstract

top
The Erdős-Faber-Lovász conjecture states that if a graph G is the union of n cliques of size n no two of which share more than one vertex, then χ(G) = n. We provide a formulation of this conjecture in terms of maximal partial clones of partial operations on a set.

How to cite

top

Lucien Haddad, and Claude Tardif. "A clone-theoretic formulation of the Erdos-Faber-Lovász conjecture." Discussiones Mathematicae Graph Theory 24.3 (2004): 545-549. <http://eudml.org/doc/270226>.

@article{LucienHaddad2004,
abstract = {The Erdős-Faber-Lovász conjecture states that if a graph G is the union of n cliques of size n no two of which share more than one vertex, then χ(G) = n. We provide a formulation of this conjecture in terms of maximal partial clones of partial operations on a set.},
author = {Lucien Haddad, Claude Tardif},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chromatic number; Erdős-Faber-Lovász conjecture; maximal partial clones; partial operations},
language = {eng},
number = {3},
pages = {545-549},
title = {A clone-theoretic formulation of the Erdos-Faber-Lovász conjecture},
url = {http://eudml.org/doc/270226},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Lucien Haddad
AU - Claude Tardif
TI - A clone-theoretic formulation of the Erdos-Faber-Lovász conjecture
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 3
SP - 545
EP - 549
AB - The Erdős-Faber-Lovász conjecture states that if a graph G is the union of n cliques of size n no two of which share more than one vertex, then χ(G) = n. We provide a formulation of this conjecture in terms of maximal partial clones of partial operations on a set.
LA - eng
KW - chromatic number; Erdős-Faber-Lovász conjecture; maximal partial clones; partial operations
UR - http://eudml.org/doc/270226
ER -

References

top
  1. [1] P. Erdős, On the Combinatorial problems which I would most like to see solved, Combinatorica 1 (1981) 25-42, doi: 10.1007/BF02579174. Zbl0486.05001
  2. [2] L. Haddad, Le treillis des clones partiels sur un univers fini et ses coatomes (Ph, D. thesis, Université de Montréal, 1986). 
  3. [3] L. Haddad and I.G. Rosenberg, Critère général de complétude pour les algèbres partielles finies, C.R. Acad. Sci. Paris, tome 304, Série I, 17 (1987) 507-509. Zbl0617.08008
  4. [4] L. Haddad, Maximal partial clones determined by quasi-diagonal relations, J. Inf. Process. Cybern. EIK 24 (1988) 7/8 355-366. Zbl0665.08004
  5. [5] L. Haddad and I.G. Rosenberg, Maximal partial clones determined by areflexive relations, Discrete Appl. Math. 24 (1989) 133-143, doi: 10.1016/0166-218X(92)90279-J. Zbl0695.08010
  6. [6] L. Haddad, I.G. Rosenberg and D. Schweigert, A maximal partial clone and a S upecki-type criterion, Acta Sci. Math. 54 (1990) 89-98. Zbl0717.08003
  7. [7] L. Haddad and I.G. Rosenberg, Completeness theory for finite partial algebras, Algebra Universalis 29 (1992) 378-401, doi: 10.1007/BF01212439. Zbl0771.08001
  8. [8] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience series in discrete mathematics and optimization, John Wiley & Sons Inc., 1995). 
  9. [9] J. Kahn, Coloring nearly-disjoint hypergraphs with n+o(n) colors, J. Combin. Theory (A) 59 (1992) 31-39, doi: 10.1016/0097-3165(92)90096-D. Zbl0774.05073

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.