PDF

Discussiones Mathematicae Graph Theory 24(3) (2004) 545-549
DOI: https://doi.org/10.7151/dmgt.1252

A CLONE-THEORETIC FORMULATION OF THE ERDOS-FABER-LOVÁSZ CONJECTURE

Lucien Haddad and Claude Tardif

Department of Mathematics and Computer Science
Royal Military College of Canada
PO Box 17000, Station "Forces"
Kingston, Ontario K7K 7B4 Canada

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.

Keywords: chromatic number, Erdős-Faber-Lovász conjecture, maximal partial clones.

2000 Mathematics Subject Classification: 05C15 (primary: graph colouring) 08A55 (secondary: Partial algebras).

References

[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.
[2]	L. Haddad, Le treillis des clones partiels sur un univers fini et ses coatomes (Ph, D. thesis, Université de Montréal, 1986).
[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.
[4]	L. Haddad, Maximal partial clones determined by quasi-diagonal relations, J. Inf. Process. Cybern. EIK 24 (1988) 7/8 355-366.
[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.
[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.
[7]	L. Haddad and I.G. Rosenberg, Completeness theory for finite partial algebras, Algebra Universalis 29 (1992) 378-401, doi: 10.1007/BF01212439.
[8]	T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience series in discrete mathematics and optimization, John Wiley & Sons Inc., 1995).
[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.

Received 12 July 2004