# A Proof of Erdös - Faber - Lovász Conjecture 111This paper is presented in
the 23rd International Conference of Forum for Interdisciplinary Mathematics
(FIM) on “Interdisciplinary Mathematical, Statistical and Computational
Techniques - 2014” organized by the NITK, Surathkal, INDIA, from 18/12/2014 to
20/12/2014.

Suresh M. H<EMAIL_ADDRESS>V. V. P. R. V. B. Suresh Dara
<EMAIL_ADDRESS>Department of Mathematical and Computational Sciences,
National Institute of Technology Karnataka, Surathkal,
Mangalore - 575025, India.

###### Abstract

In 1972, Erdös - Faber - Lovász (EFL) conjectured that, if 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. In 1978, Deza, Erdös and Frankl had given an equivalent
version of the same for graphs: Let $G=\bigcup_{i=1}^{n}A_{i}$ denote a graph
with $n$ complete graphs $A_{1},A_{2},$ $\dots,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 an
algorithmic proof of the conjecture using the symmetric latin squares and
clique degrees of the vertices of $G$.

###### keywords:

Chromatic number , Erdös - Faber - Lovász conjecture , Latin squares

###### MSC:

[2010] 05A05 , 05B15 , 05C15

##  1 Introduction

One of the famous conjectures in graph theory is Erdös - Faber - Lovász
conjecture. It states that if H is a linear hypergraph consisting of $n$ edges
of cardinality $n$, then it is possible to color the vertices of H with $n$
colors so that no two vertices with the same color are in the same edge [1].
Erdös, in 1975, offered 50 pounds [2, 3] and in 1981, offered 500USD [4, 5]
for the proof or disproof of the conjecture. Kahn [6] showed that the
chromatic number of H is at most $n+o(n)$. Jakson et al. [7] proved that the
conjecture is true when the partial hypergraph $S$ of H determined by the
edges of size at least three can be $\Delta_{S}$-edge-colored and satisfies
$\Delta_{S}\leq 3$. In particular, the conjecture holds when $S$ is unimodular
and $\Delta_{S}\leq 3$. Viji Paul et al. [8] established the truth of the
conjecture for all linear hypergraphs on $n$ vertices with
$\Delta(\textbf{H})\leq\sqrt{n+\sqrt{n}+1}$. Sanhez - Arrayo [3] proved the
conjecture for dense hypergraphs. Faber [9] proves that for fixed degree,
there can be only finitely many counterexamples to EFL on this class (both
regular and uniform) of hypergraphs. We consider the equivalent version of the
conjecture for graphs given by Deza, Erdös and Frankl in 1978 [10, 3, 5, 11].

###### Conjecture 1.1

Let $G=\bigcup_{i=1}^{n}A_{i}$ denote a graph with $n$ complete graphs
$(A_{1},A_{2},$ $\dots,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$.

###### Definition 1.2

Let $G=\bigcup_{i=1}^{n}A_{i}$ denote a graph with $n$ complete graphs
$A_{1},A_{2},$ $\dots,A_{n}$, each having exactly $n$ vertices and the
property that every pair of complete graphs has at most one common vertex. The
clique degree $d^{K}(G)$ of a vertex $v$ in $G$ is given by
$d^{K}(v)=|\\{A_{i}:v\in V(A_{i}),1\leq i\leq n\\}|$. The maximum clique
degree $\Delta^{K}(G)$ of the graph $G$ is given by $\Delta^{K}(G)=max_{v\in
V(G)}d^{K}(v)$.

From the above definition one can observe that degree of a vertex in
hypergraph is same as the clique degree of a vertex in a graph.

###### Definition 1.3

Let $G_{1}$ and $G_{2}$ be two vertex disjoint graphs, and let $x_{1},x_{2}$
be two vertices of $G_{1},G_{2}$ respectively. Then, the graph $G(x_{1}x_{2})$
obtained by merging the vertices $x_{1}$ and $x_{2}$ into a single vertex is
called the concatenation of $G_{1}$ and $G_{2}$ at the points $x_{1}$ and
$x_{2}$ (see [12]).

###### Definition 1.4

A latin square is an $n\times n$ array containing $n$ different symbols such
that each symbol appears exactly once in each row and once in each column.
Moreover, a latin square of order $n$ is an $n\times n$ matrix $M=[m_{ij}]$
with entries from an $n$-set $V=\\{1,2,\dots,n\\}$, where every row and every
column is a permutation of $V$ (see [13]). If the matrix $M$ is symmetric,
then the latin square is called symmetric latin square.

##  2 Results

We know that a symmetric $n\times n$ matrix is determined by
$\frac{n(n+1)}{2}$ scalars. Using symmetric latin squares we give an
$n$-coloring of $H_{n}$ constructed below. Then using the $n$-coloring of
$H_{n}$ we give an $n$-coloring of all the other graphs $G$ satisfying the
hypothesis of Conjecture 1.1.

Construction of $H_{n}$:

Let $n$ be a positive integer and $B_{1},B_{2},\dots,B_{n}$ be $n$ copies of
$K_{n}$. Let the vertex set
$V(B_{i})=\\{a_{i,1},a_{i,2},a_{i,3},\dots,a_{i,n}\\}$, $1\leq i\leq n$.

Step 1.

Let $H^{1}=B_{1}$.

Step 2.

Consider the vertices $a_{1,2}$ of $H^{1}$ and $a_{2,1}$ of $B_{2}$. Let
$b_{1,2}$ be the vertex obtained by the concatenation of the vertices
$a_{1,2}$ and $a_{2,1}$. Let the resultant graph be $H^{2}$.

Step 3.

Consider the vertices $a_{1,3}$, $a_{2,3}$ of $H^{2}$ and $a_{3,1}$, $a_{3,2}$
of $B_{3}$. Let $b_{1,3}$ be the vertex obtained by the concatenation of
vertices $a_{1,3}$, $a_{3,1}$ and let $b_{2,3}$ be the vertex obtained by the
concatenation of vertices $a_{2,3}$, $a_{3,2}$. Let the resultant graph be
$H^{3}$.

Continuing in the similar way, at the $n$th step we obtain the graph
$H^{n}=H_{n}$ (for the sake of convenience we take $H^{n}$ as $H_{n}$).

By the construction of $H_{n}$ one can observe the following:

  1. 1.

$H_{n}$ is a connected graph and satisfying the hypothesis of Conjecture 1.1.

  2. 2.

$H_{n}$ has exactly $n$ verticies of clique degree one and $\frac{n(n-1)}{2}$
vertices of clique degree $2$ (each $B_{i}$ has exactly $(n-1)$ vertices of
clique degree $2$ and one vertex of clique degree one, $1\leq i\leq n$).

  3. 3.

$H_{n}=\bigcup_{i=1}^{n}B_{i}$, where $B_{i}=A_{i}$ and $B_{i}$, $B_{j}$ have
exactly one common vertex for $1\leq i<j\leq n$.

  4. 4.

$H_{n}$ has exactly $\frac{n(n+1)}{2}$ vertices.

  5. 5.

One can observe that in a connected graph $G$ if clique degree increases the
number of vertices also increases, from this it follows that, $H_{n}$ is the
graph with minimum number of vertices satisfying the hypothesis of Conjecture
1.1. If all the vertices of $G$ are of clique degree one, then $G$ will have
$n^{2}$ vertices. Thus, $\frac{n(n+1)}{2}\leq|V(G)|\leq n^{2}$.

###### Lemma 2.1

If $G$ is a graph satisfying the hypothesis of Conjecture 1.1, then $G$ can be
obtained from $H_{n}$ for some $n$ in $\mathbb{N}$.

Proof: Let $G$ be a graph satisfying the hypothesis of Conjecture 1.1. Let
$b_{x}$ be the new labeling to the vertices $v$ of clique degree greater than
one in $G$, where $x=\\{i$ : vertex $v$ is in $A_{i}\\}$. Define
$N_{i}=\\{b_{x}:|x|=i\\}$ for $i=2,3,\dots,n$. Then the graph $G$ is
constructed from $H_{n}$ as given below:

Step 1: For every common vertex $b_{i,j}$ in $H_{n}$ which is not in $N_{2}$,
split the vertex $b_{i,j}$ into two vertices $u_{i,j},u_{j,i}$ such that
vertex $u_{i,j}$ is adjacent only to the vertices of $B_{i}$ and the vertex
$u_{j,i}$ is adjacent only to the vertices of $B_{j}$ in $H_{n}$.

Step 2: For every vertex $b_{x}$ in $N_{i}$ where $i=3,4,\dots,n$, merge the
vertices
$u_{l_{1},l_{2}},u_{l_{2},l_{3}},\dots,u_{l_{m-1},l_{m}},u_{l_{m},l_{1}}$ into
a single vertex $u_{x}$ in $H_{n}$ where $l_{i}\in x$ and $l_{i}<l_{j}$ for
$i<j$.

Let $G^{\prime}$ be the graph obtained in Step 2. Let $V(B_{i}^{\prime})$,
$V(A_{i}^{\prime})$ be the set of all clique degree 1 vertices of $B_{i}$ of
$G^{\prime}$, $A_{i}$ of $G$ respectively, $1\leq i\leq n$. Thus by splitting
all the common vertices of $H_{n}$ which are not in $N_{2}$ and merging the
vertices of $H_{n}$ corresponding to the vertices in $N_{i},i\geq 3$, we get
the graph $G^{\prime}$. One can observe that
$|V(A_{i}^{\prime})|=|V(B_{i}^{\prime})|$, $1\leq i\leq n$. Define a function
$f:V(G)\rightarrow V(G^{\prime})$ by

$\displaystyle f(b_{i,j})$ $\displaystyle=b_{i,j}$ $\displaystyle\text{ for
}b_{i,j}\in N_{2}$ $\displaystyle f(b_{i_{1},i_{2},\dots i_{k}})$
$\displaystyle=u_{i_{1},i_{2},\dots i_{k}}$ $\displaystyle\text{ for
}b_{ii_{1},i_{2},\dots i_{k}}\in\cup_{i=3}^{n}N_{i}$ $\displaystyle
f|_{V(A_{i}^{\prime})}$ $\displaystyle=g_{i}$ $\displaystyle(\text{any 1-1 map
}g_{i}:V(A_{i}^{\prime})\rightarrow V(B_{i}^{\prime})),\text{ for }1\leq i\leq
n$

One can observe that $f$ is an isomorphism from $G$ to $G^{\prime}$.

From Lemma 2.1, one can observe that in $G$ there are at most
${\frac{n(n-1)}{2}}$ common vertices.

Let $G$ be the graph satisfying the hypothesis of Conjecture 1.1. Let
$\hat{H}$ be the graph obtained by removing the vertices of clique degree one
from graph $G$. i.e. $\hat{H}$ is the induced subgraph of $G$ having all the
common vertices of $G$.

###### Lemma 2.2

The chromatic number of $H_{n}$ is $n$.

Proof: Let $H_{n}$ be the graph defined as above. Let $M$ (given below) be an
$n\times n$ matrix in which an entry $m_{i,j}=b_{i,j}$, is a vertex of
$H_{n}$, belonging to both $B_{i},B_{j}$ for $i\neq j$ and $m_{ii}=a_{i,i}$ is
the vertex of $H_{n}$ which belongs to $B_{i}$. i.e.,

M=$\left(\begin{array}[]{ccccc}a_{1,1}&b_{1,2}&b_{1,3}&\dots&b_{1,n}\\\
b_{1,2}&a_{2,2}&b_{2,3}&\dots&b_{2,n}\\\
b_{1,3}&b_{2,3}&a_{3,3}&\dots&b_{3,n}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
b_{1,n}&b_{2,n}&b_{3,n}&\dots&a_{n,n}\\\ \end{array}\right)$

Clearly $M$ is a symmetric matrix. We know that, for every $n$ in $\mathbb{N}$
there is a symmetric latin square (see [14]) of order $n\times n$. Bryant and
Rodger [15] gave a necessary and sufficient condition for the existence of an
$(n-1)$-edge coloring of $K_{n}$ (n even), and $n$-edge coloring of $K_{n}$ (n
odd) using symmetric latin squares. Let $v_{1},v_{2},\dots,v_{n}$ be the
vertices of $K_{n}$ and $e_{ij}$ is the edge joining the vertices $v_{i}$ and
$v_{j}$ of $K_{n}$, where $i<j$, then arrange the edges of $K_{n}$ in the
matrix form $A=[a_{i,j}]$ where $a_{i,j}=e_{i,j}$, $a_{j,i}=e_{i,j}$ for $i<j$
and $a_{i,i}=0$ for $1\leq i\leq n$, we have
$A=\left(\begin{array}[]{ccccc}0&e_{1,2}&e_{1,3}&\dots&e_{1,n}\\\
e_{1,2}&0&e_{2,3}&\dots&e_{2,n}\\\ e_{1,3}&e_{2,3}&0&\dots&e_{3,n}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ e_{1,n}&e_{2,n}&e_{3,n}&\dots&0\\\
\end{array}\right)$

and let $V$ is a matrix given by

$V=\left(\begin{array}[]{ccccc}v_{1}&0&0&\dots&0\\\ 0&v_{2}&0&\dots&0\\\
0&0&v_{3}&\dots&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
0&0&0&\dots&v_{n}\\\ \end{array}\right)$. Then, define a matrix $A^{\prime}$
as

$A^{\prime}=A+V=\left(\begin{array}[]{ccccc}v_{1}&e_{1,2}&e_{1,3}&\dots&e_{1,n}\\\
e_{1,2}&v_{2}&e_{2,3}&\dots&e_{2,n}\\\ e_{1,3}&e_{2,3}&v_{3}&\dots&e_{3,n}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\ e_{1,n}&e_{2,n}&e_{3,n}&\dots&v_{n}\\\
\end{array}\right)$.

Let $C=[c_{i,j}]$ be a matrix where $c_{i,j}$ ($i\neq j$), is the color of
$e_{i,j}$ (i.e., $c_{i,j}=c(e_{i,j})$) and $c_{i,i}$ is the color of $v_{i}$.
We call $C$ the color matrix of $A^{\prime}$. Then $C$ is the symmetric latin
square (see[15]). As the elements of $M$ are the vertices of $H_{n}$, one can
assign the colors to the vertices of $H_{n}$ from the color matrix $C$, by the
color $c_{i,j}$ (where $c_{i,j}$ denotes the value at the $(i,j)$-th entry in
the color matrix $C$), for $i,j=1,2,\dots,n$ and $i\neq j$ to the vertex
$b_{i,j}$ in $H_{n}$ and the color $c_{i,i}$ (where $c_{i,i}$ denotes the
value at the $(i,i)$-th entry in the color matrix $C$), for $i=1,2,\dots n$ to
the vertex $a_{i,i}$ in $H_{n}$. Hence $H_{n}$ is $n$ colorable.

As $H_{n}$ is the graph satisfying the hypothesis of Conjecture 1.1. With
using the coloring of $H_{n}$ which is the graph satisfying the hypothesis of
Conjecture 1.1 we extend the $n$-coloring of all possible graphs $G$
satisfying the hypothesis of Conjecture 1.1.

###### Theorem 2.3

If $G$ is a graph satisfying the hypothesis of Conjecture 1.1, then $G$ is
$n$-colorable.

Proof: Let $G$ be a graph satisfying the hypothesis of Conjecture 1.1. Let
$\hat{H}$ be the induced subgraph of $G$ consisting of the vertices of clique
degree greater than one in $G$. For every vertex $v$ of clique degree greater
than one in $G$, label the vertex $v$ by $u_{A}$ where $A=\\{i:v\in
A_{i};i=1,2,\dots,n\\}$. Define $X=\\{b_{i,j}:A_{i}\cap A_{j}=\emptyset\\}$,
$X_{i}=\\{v\in G:d^{K}(v)=i\\}$ for $i=1,2,\dots,m$.

Let $1,2,\dots,n$ be the $n$-colors and $C$ be the color matrix( of size
$n\times n$) as defined in the proof of Lemma 2.2. The following construction
applied on the color matrix $C$, gives a modified color matrix $C_{M}$, using
which we assign the colors to the graph $\hat{H}$. Then this coloring can be
extended to the graph $G$. Construct a new color matrix $C_{1}$ by putting
$c_{i,j}=0,c_{j,i}=0$ for every $b_{i,j}$ in $X$. Also, let $c_{i,i}=0$ for
each $i=1,2,\dots,n$

Construction:

Let $T=\cup_{i=3}^{n}X_{i}$, $P=\emptyset$, $T^{\prime\prime}=X_{2}$ and
$P^{\prime\prime}=\emptyset$.

Step 1:

If $T=\emptyset$, let $C_{m}$ be the color matrix obtained in Step 4 and go to
Step 5. Otherwise, choose a vertex $u_{i_{1},i_{2},\dots,i_{m}}$ from $T$,
where $i_{1}<i_{2}<\dots<i_{m}$, and then choose $\binom{m}{2}$ vertices
$b_{i_{1},i_{2}}$, $b_{i_{1},i_{3}}$, $\dots$, $b_{i_{1},i_{m}}$,
$b_{i_{2},i_{3}}$, $\dots$, $b_{i_{m-1},i_{m}}$ from $V(H_{n})$ corresponding
to the set $\\{i_{1},i_{2},\dots,i_{m}\\}$. Take
$T^{\prime}=\\{b_{i_{1},i_{2}},b_{i_{1},i_{3}},\dots,b_{i_{1},i_{m}},b_{i_{2},i_{3}},\dots,b_{i_{m-1},i_{m}}\\}$
and $P^{\prime}=\emptyset$. Let $T_{1}^{\prime}=\\{b_{i,j}:b_{i,j}\in
T^{\prime},c(b_{i,j})$ appears more than once in the $i^{th}$ row or $j^{th}$
column in $C\\}$ and $T_{2}^{\prime}=\\{b_{i,j}:b_{i,j}\in
T^{\prime},c(b_{i,j})$ appears exactly once in the $i^{th}$ row and $j^{th}$
column in $C\\}$. If $T_{1}^{\prime}\neq\emptyset$ choose a vertex $b_{s,t}$
from $T_{1}^{\prime}$, otherwise choose a vertex $b_{s,t}$ from
$T_{2}^{\prime}$. Then add the vertex $b_{s,t}$ to $P^{\prime}$ and remove it
from $T^{\prime}$. Go to Step 2.

Step 2:

If $T_{2}^{\prime}\neq\emptyset$ go to Step 3. Otherwise, choose a vertex
$b_{i_{m-1},i_{m}}$ from $T_{1}^{\prime}$. Let $A=\\{c_{i,j}:c_{i,j}\neq
0;i=i_{m-1},1\leq j\leq n\\}$, $B=\\{c_{i,j}:c_{i,j}\neq 0;j=i_{m},1\leq i\leq
n\\}$. If $|A\cap B|<n$ then, construct a new color matrix $C_{2}$, replacing
$c_{i_{m-1},i_{m}}$, $c_{i_{m},i_{m-1}}$ by $x$, where
$x\in\\{1,2,\dots,n\\}\setminus A\cup B$. Then add the vertex
$b_{i_{m-1},i_{m}}$ to $T_{2}^{\prime}$ and remove it from $T_{1}^{\prime}$.
Go to Step 3. Otherwise choose a color $x$ which appears exactly once either
in $i_{m-1}^{th}$ row or in $i_{m}^{th}$ column of the color matrix and
construct a new color matrix $C_{2}$ replacing $c_{i_{m-1},i_{m}}$,
$c_{i_{m},i_{m-1}}$ by $x$. Then add the vertex $b_{i_{m-1},i_{m}}$ to
$T_{2}^{\prime}$ and remove it from $T_{1}^{\prime}$. Go to Step 3.

Step 3:

If $T^{\prime}=\emptyset$, then add the vertex $u_{i_{1},i_{2},\dots,i_{m}}$
to $P$ and remove it from $T$, go to Step 1. Otherwise, if $T^{\prime}\cap
T_{1}^{\prime}\neq\emptyset$ choose a vertex $b_{i,j}$ from $T^{\prime}\cap
T_{1}^{\prime}$, if not choose a vertex $b_{i,j}$ from $T^{\prime}\cap
T_{2}^{\prime}$. Go to Step 4.

Step 4:

Let $c(b_{i,j})=x,\ c(b_{s,t})=y$. If $c(b_{i,j})=c(b_{s,t})$, then add the
vertex $b_{i,j}$ to $P^{\prime}$ and remove it from $T^{\prime}$. Go to Step
3. Otherwise, let $A=\\{c_{l,m}:c_{l,m}=x\\}$,
$B=\\{c_{l,m}:c_{l,m}=y\\}\setminus\\{c_{l,m},c_{m,l}:b_{l,m}\in
P^{\prime},l<m\\}$. Construct a new color matrix $C_{3}$ by putting
$c_{l,m}=y$ for every $c_{l,m}$ in $A$ and $c_{l,m}=x$ for every $c_{l,m}$ in
B. Then add the vertex $b_{i,j}$ to $P^{\prime}$ and remove it from
$T^{\prime}$. Go to Step 3.

Step 5:

If $T^{\prime\prime}=\emptyset$ consider $C_{M}=C_{m_{1}}$ stop the process.
Otherwise, choose a vertex $u_{i,j}$ from $T^{\prime\prime}$ and go to Step 6.

Step 6:

If $c_{i,j}$ appears exactly once in both $i^{th}$ row and $j^{th}$ column of
the color matrix $C_{m}$, then add the vertex $b_{i,j}$ to $P^{\prime\prime}$
and remove it from $T^{\prime\prime}$, go to Step 5. Otherwise let
$A=\\{c_{i,j}:c_{i,j}\neq 0;1\leq j\leq n\\}$, $B=\\{c_{i,j}:c_{i,j}\neq
0;1\leq i\leq n\\}$. Construct a new color matrix $C_{m_{1}}$ by putting $x$
in $c_{i,j}$, $c_{j,i}$ where $x\in\\{1,2,\dots,n\\}\setminus A\cup B$. Then
add the vertex $u_{i,j}$ to $P^{\prime\prime}$ and remove it from
$T^{\prime\prime}$, go to Step 5.

Thus, in step 6, we get the modified color matrix $C_{M}$. Then, color the
vertex $v$ of $\hat{H}$ by $c_{i,j}$ of $C_{M}$, whenever $v\in A_{i}\cap
A_{j}$. Then, extend the coloring of $\hat{H}$ to $G$ by assigning the
remaining colors which are not used for $A_{i}$ from the set of $n$-colors, to
the vertices of clique degree one in $A_{i}$, $1\leq i\leq n$. Thus $G$ is
$n$-colorable.

###### Corollary 2.4

[3] Consider a linear hypergraph H consisting of $n$ edges each of size at
most $n$ and $\delta(\textbf{H})\geq 2$. If $H$ is dense then
$\chi(\textbf{H})\leq n$.

## References

## References

  * [1] C. Berge, On two conjectures to generalize Vizing’s theorem, Matematiche (Catania) 45 (1) (1990) 15–23 (1991), graphs, designs and combinatorial geometries (Catania, 1989).
  * [2] P. Erdős, Problems and results in graph theory and combinatorial analysis, Proc. British Combinatorial Conj., 5th (1975) 169–192.
  * [3] A. Sánchez-Arroyo, The Erdős-Faber-Lovász conjecture for dense hypergraphs, Discrete Math. 308 (5-6) (2008) 991–992.
  * [4] P. Erdős, On the combinatorial problems which i would most like to see solved, Combinatorica 1 (1) (1981) 25–42.
  * [5] T. R. Jensen, B. Toft, Graph coloring problems, Vol. 39, John Wiley & Sons, 2011\.
  * [6] J. Kahn, Coloring nearly-disjoint hypergraphs with $n+o(n)$ colors, Journal of Combinatorial Theory, Series A 59 (1) (1992) 31–39.
  * [7] B. Jackson, G. Sethuraman, C. Whitehead, A note on the Erdős-Farber-Lovász conjecture, Discrete Math. 307 (7-8) (2007) 911–915.
  * [8] V. Paul, K. A. Germina, On edge coloring of hypergraphs and Erdös-Faber-Lovász conjecture, Discrete Math. Algorithms Appl. 4 (1) (2012) 1250003, 5.
  * [9] V. Faber, The Erdős-Faber-Lovász conjecture—the uniform regular case, J. Comb. 1 (2) (2010) 113–120.
  * [10] M. Deza, P. Erdös, P. Frankl, Intersection properties of systems of finite sets, Proceedings of the London Mathematical Society 3 (2) (1978) 369–384.
  * [11] J. Mitchem, R. L. Schmidt, On the Erdős-Faber-Lovász conjecture, Ars Combin. 97 (2010) 497–505.
  * [12] S. Kundu, E. Sampathkumar, J. Shearer, D. Sturtevant, Reconstruction of a pair of graphs from their concatenations, SIAM Journal on Algebraic Discrete Methods 1 (2) (1980) 228–231.
  * [13] C. F. Laywine, G. L. Mullen, Discrete mathematics using Latin squares, Vol. 17, Wiley New York, 1998.
  * [14] X. Ye, Y. Xu, On the number of symmetric latin squares, in: Computer Science and Service System (CSSS), 2011 International Conference on, IEEE, 2011, pp. 2366–2369.
  * [15] D. Bryant, C. Rodger, On the completion of latin rectangles to symmetric latin squares, Journal of the Australian Mathematical Society 76 (1) (2004) 109–124.