×

Further results on Erdős-Faber-Lovász conjecture. (English) Zbl 1473.05089

Summary: In 1972, Erdős-Faber-Lovász (EFL) conjectured that, if \(\mathcal{H}\) is a linear hypergraph consisting of \(n\) edges of cardinality \(n\), then it is possible to color the vertices with \(n\) colors so that no two vertices with the same color are in the same edge. M. Deza et al. [Proc. Lond. Math. Soc. (3) 36, 369–384 (1978; Zbl 0407.05006)] had given an equivalent version of the same for graphs: Let \(G = \bigcup^n_{i=1} A_i\) denote a graph with \(n\) complete graphs \(A_1, A_2, \ldots, A_n\), each having exactly \(n\) vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of \(G\) is \(n\). The clique degree \(d^K (v)\) of a vertex \(v\) in \(G\) is given by \(d^K (v) = |\{A_i : v \in V(A_i), 1 \leq i \leq n\} |\). In this paper we give a method for assigning colors to the graphs satisfying the hypothesis of the Erdős-Faber-Lovász conjecture and every \(A_i\) \((1 \leq i \leq n)\) has atmost \(\frac{n}{2}\) vertices of clique degree greater than one using Symmetric latin Squares and clique degrees of the vertices of \(G\).

MSC:

05C15 Coloring of graphs and hypergraphs
05B15 Orthogonal arrays, Latin squares, Room squares
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, Claude, On two conjectures to generalize Vizing’s theorem, Matematiche (Catania), 45, 1, 15-23 (1991) (1990) · Zbl 0739.05037
[2] Erdős, PAUL, Problems and results in graph theory and combinatorial analysis, Proc. British Combinatorial Conj., 5th, 169-192 (1975) · Zbl 0335.05002
[3] Erdős, Pál, On the combinatorial problems which i would most like to see solved, Combinatorica, 1, 1, 25-42 (1981) · Zbl 0486.05001
[4] Jensen, Tommy R.; Toft, Bjarne, Graph Coloring Problems, Vol. 39 (2011), John Wiley & Sons · Zbl 0855.05054
[5] Chang, William I.; Lawler, Eugene L., Edge coloring of hypergraphs and a conjecture of Erdös, Faber, Lovász, Combinatorica, 8, 3, 293-295 (1988) · Zbl 0661.05026
[6] Kahn, Jeff, Coloring nearly-disjoint hypergraphs with \(####\) colors, J. Combin. Theory Ser. A, 59, 1, 31-39 (1992) · Zbl 0774.05073
[7] Jackson, Bill; Sethuraman, G.; Whitehead, Carol, A note on the Erdős-Farber-Lovász conjecture, Discrete Math., 307, 7-8, 911-915 (2007) · Zbl 1114.05035
[8] Paul, Viji; Germina, K. A., On edge coloring of hypergraphs and Erdös-Faber-Lovász conjecture, Discrete Math. Algorithms Appl., 4, 1, 1250003 (2012) · Zbl 1247.05086
[9] Sánchez-Arroyo, Abdón, The Erdős-Faber-Lovász conjecture for dense hypergraphs, Discrete Math., 308, 5-6, 991-992 (2008) · Zbl 1139.05025
[10] Deza, M.; Erdös, P.; Frankl, P., Intersection properties of systems of finite sets, Proc. Lond. Math. Soc., 3, 2, 369-384 (1978) · Zbl 0407.05006
[11] Mitchem, John; Schmidt, Randolph L., On the Erdős-Faber-Lovász conjecture, Ars Combin., 97, 497-505 (2010) · Zbl 1249.05131
[12] Haddad, Lucien; Tardif, Claude, A clone-theoretic formulation of the Erdös-Faber-Lovász conjecture, Discuss. Math. Graph Theory, 24, 3, 545-549 (2004) · Zbl 1065.05040
[13] Kundu, Sukhamay; Sampathkumar, E.; Shearer, James; Sturtevant, Dean, Reconstruction of a pair of graphs from their concatenations, SIAM J. Algebr. Discrete Methods, 1, 2, 228-231 (1980) · Zbl 0499.05044
[14] Laywine, Charles F.; Mullen, Gary L., Discrete Mathematics using Latin Squares, Vol. 17 (1998), Wiley New York · Zbl 0957.05002
[15] Ye, Xiaorui; Xu, Yunqing, On the number of symmetric latin squares, Computer Science and Service System (CSSS), 2011 International Conference on, 2366-2369 (2011), IEEE
[16] Bryant, Darryn; Rodger, CA, On the completion of latin rectangles to symmetric latin squares, J. Aust. Math. Soc., 76, 1, 109-124 (2004) · Zbl 1051.05013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.