Chapter 3 Embedding edge-coloured free-type graphs

3.1 Embedding edge-coloured free-type graphs

According to Lemma \[lem1560\] and Lemma \[lem1570\] the problem of giving necessary and sufficient conditions for embedding an externally diagonally prescribed symmetric latin rectangle in some latin square is the same as the problem of giving necessary and sufficient conditions for embedding proper edge-coloured \(r\)-free-type graph with no free-edges in some proper edge-coloured complete graph. The former problem was solved by Andersen and, independently, Hoffman who both proved Theorem \[thm1440\]. Theorem \[thm1440\] says that the necessary conditions of admissibility and being Ryser are sufficient. These conditions have their obvious analogues in the language of edge-coloured free-type graphs.

\[def1590\] If \(\cG=(G,(C,\phi))\) is an edge-coloured \(r\)-free-type graph of order \(n\) then \(\ek=e(\cG,c_k)=|\{e\in E(G^{\star})\backslash L(G^{\star})\,|\,\phi(e)=c_k\}|\), \(\lk=l(\cG,c_k)=|\{e\in L(G^{\star})\,|\,\phi(e)=c_k\}|\), \(\Ek=\Erk=|\{e\in F(G)\,|\,\phi(e)=c_k\}|\) and \(\Lk=\Lrk=|\{e\in L(G)\backslash L(G^{\star})\,|\,\phi(e)=c_k\}|\).

Or, to put it another way, \(\ek\) is the number of non-loop edges of \(G^{\star}\) of colour \(c_k\), \(\lk\) is the number of loops of \(G^{\star}\) of colour \(c_k\), \(\Ek\) is the number of free-edges of colour \(c_k\) and \(\Lk\) is the number of free-loops of colour \(c_k\).

\[def1600\] A proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) is Ryser if and only (\[def16001\]) holds for all \(c_k\in C\)

1. \(2\ek+\lk\geq 2r-n+2\Ek+\Lk\) \[def16001\]

\[def1610\] If \(\cH\) is a proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) then \(O(\cH)=\{c_k\in C\,|\,\lk+\Lk\equiv (n+1)\bmod{2}\}\) and \(o(\cH)=|O(\cH)|\).

\[def1620\] A proper \(C\)-edge-coloured \(r\)-free-type graph of order \(n\) is admissible if and only if \(n\) is odd and \(\lk+\Lk\leq 1\) for all \(c_k\in C\) or \(n\) is even and \(o(\cH)\leq 2|F|\).

Now Theorem \[thm1440\] can be translated into a result about embedding edge-coloured free-type graphs.

\[Andersen, Hoffman\] \[thm1630\] An \(n\)-edge-coloured \(r\)-free-type graph of order \(n\) with no free-edges can be embedded in an \(n\)-edge-coloured complete graph of order \(n\) if and only if \(\cH\) is Ryser admissible.

Now there is an obvious question. Is being Ryser admissible sufficient for embedding an \(n\)-edge-coloured \(r\)-free-type graph \(\cH\) if \(F(\cH)\neq\emptyset\)? The proper \(C_{[8]}\)-edge-coloured \(3\)-free-type graph \(\cH\) of order \(8\) in Figure \[fig1650\] is an example of how being Ryser and admissible is insufficient, in general, for embedding an \(n\)-edge-coloured \(r\)-free-type graphs of order \(n\) in an \(n\)-edge-coloured complete graph of order \(n\). \(\cH\) is Ryser because \(2r-n+2\Ek+\Lk\leq 0\) for all \(c_k\in C_{[8]}=\{c_i\,|\,i\in [8]\}\) and admissible because \(n\) is even, \(o(\cH)=|\{c_1,c_3\}|=2\) and \(o(\cH)\leq 2|F|=2\). However, \(\cH\) cannot be embedded in a proper \(C_{[8]}\)-edge-coloured complete graph of order \(8\) because \(c_1\in O(\cH)\) and yet every vertex which is the end of no loop is the end of an edge of colour \(c_1\).

A \(C_{[8]}\)-edge-coloured \(3\)-free-type graph

Even if there are no free-loops then being Ryser admissible is generally insufficient. The \(C_{[8]}\)-edge-coloured \(r\)-free-type graph \(\cH\) of order \(8\) in Figure \[fig1660\] is Ryser because \(2r-n+2\Ek+\Lk=0\) for all \(c_k\in C_{[8]}\backslash\{c_1,c_2\}\), \(2r-n+2\Ek+\Lk=2\) for \(c_k\in\{c_1,c_2\}\) and \(2\ek+\lk=4\) for \(c_k\in\{c_1,c_2\}\). Moreover, \(\cH\) is admissible because \(n\) is even \(o(\cH)=|\{c_3,c_4,c_5,c_6\}|=4\) and \(2|F|=4=o(\cH)\). However, \(\cH\) cannot be embedded in a proper \(C_{[8]}\)-edge-coloured complete graph of order \(8\). If \(\cH\) were embedded in a proper \(C_{[8]}\)-edge-coloured complete graph \(\cK\) of order \(8\) then, because every vertex is the end of eight edges, every vertex is the end of some edge of every colour. Therefore \(v\), for instance, is the end of an edge of colour \(c_1\). This end cannot be a non-loop edge because every remaining vertex except \(w\) is the end of an edge of colour \(c_1\) and \(vw\) has colour \(c_2\). Moreover, the edge of colour \(c_1\) with \(v\) as an end cannot be a loop because every vertex is the end of a loop of some colour in \(\{c_3,c_4,c_5,c_6\}\).

A \(C_{[8]}\)-edge-coloured \(4\)-free-type graph

In this thesis the ultimate aim is to prove Theorem \[thm5550\] which gives necessary and sufficient conditions for a proper \(C_{[n]}\)-edge-coloured \(r\)-free-type graph of order \(n\) with no free-loops to be embeddable in some proper \(C_{[n]}\)-edge-coloured complete graph of order \(n\).

Of course the ultimate aim of this line of research would be to generalise Theorems \[1440\] and \[thm5550\] to give necessary and sufficient conditions without either the condition for no free loops nor the condition for no free edges. Unfortunately this result still seems to be a long way out of reach.

In terms of symmetric latin squares Theorem \[thm5550\] characterises the \(r\times r\) symmetric latin rectangles which can be embedded in a symmetric latin square of order \(n\) with prescribed independent non-diagonal cells.

\[def1680\] In a latin square \(L\) cells \((i,j)\) and \((k,l)\) are independent if and only if \(i\neq j\) and \(k\neq l\).

\[def1690\] An external non-diagonal prescription of order on is a map \(g:\Sigma\rightarrow [(n-r)/2]^{\star}\) which satisfies \(g(\Sigma)\leq (n-r)/2\)

\[def1700\] If \(R\) is an \(r\times r\) symmetric latin rectangle on \(\Sigma\) and \(g\) is an external non-diagonal prescription of order \((n-r)/2\) then \(R\) is -embedded in a symmetric latin square of order \(n\) if and only if there are \(2g(\sigma)\) independent cells containing symbol \(\sigma\) outside \(R\) for all \(\sigma\in\Sigma\).

\[def1710\] An externally non-diagonally prescribed latin rectangle on is a pair \((R,g)\) where \(R\) is an \(r\times r\) latin rectangle on \(\Sigma\) and \(g\) is an external non-diagonal prescription of order \((n-r)/2\) on \(\Sigma\).

\[def1720\] An externally non-diagonally prescribed \(r\times r\) latin rectangle \((R,g)\) is embedded in a latin square \(L\) of order \(n\) if and only if \(R\) is \(g\)-embedded in \(L\).

The more general result which is still out of reach, in this context, is about embedding latin rectangles with general external prescription.

\[def1740\] An external prescription of order on is a pair \((f,g)\) where \(f\) is a diagonal prescription of order \(k(f)\) on \(\Sigma\) and \(g\) is a non-diagonal prescription of order \(k(g)\) and \(k(f)+2k(g)=n-r\).

\[def1750\] If \(R\) is an \(r\times r\) symmetric latin rectangle on \(\Sigma\), \(f\) is an external diagonal prescription of order \(n-r\) on \(\Sigma\) and \(g\) is an external non-diagonal prescription of order \((n-r)/2\) on \(\Sigma\) then \(R\) is -embedded in a symmetric latin square of order \(n\) if and only if there are \(f(\sigma)\) main diagonal cells outside \(R\) containing \(\sigma\) and \(2g(\sigma)\) independent cells outside containing symbol \(\sigma\) for all \(\sigma\in\Sigma\).

\[def1760\] An externally prescribed symmetric latin rectangle of order on is a pair \((R,(f,g))\) where \(R\) is an \(r\times r\) latin rectangle on \(\Sigma\) and \((f,g)\) is an external prescription of order \(n-r\) on \(\Sigma\).

\[def1770\] An externally prescribed \(r\times r\) symmetric latin rectangle \((R,(f,g))\) is embedded in a latin square \(L\) of order \(n\) if and only if \(R\) is \((f,g)\)-embedded in \(L\).

\[prob1780\] Characterise the externally prescribed \(r\times r\) symmetric latin rectangles on \(\Sigma\) which can be embedded in some symmetric latin square of order \(n\) on \(\Sigma\).

3.2 Embedding edge-coloured free-type simple graphs

Although the correspondence between symmetric latin squares and proper edge-coloured complete graphs introduced in Section \[sec885\] seems the most natural when it comes to symmetric latin squares of odd order there is an alternative correspondence with complete simple graphs of even order.

For example, the proper \([3]\)-edge-coloured complete graph of order \(3\) corresponding to the \(3\times 3\) latin square in Figure \[fig1800\] is shown on the left of Figure \[fig1810\]. There is an obvious correspondence between the proper \([3]\)-edge-coloured complete graph of order \(3\) on the left of Figure \[fig1810\] and the proper \([3]\)-edge-coloured complete simple graph of order \(4\) on the right of the same figure.

\(\left[\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{array}\right]\)

Edge-coloured complete graph and complete simple graph

For symmetric latin squares of even order this correspondence is lost because of the possibility of having more than one loop of the same colour.

\[def1850\] The edge-coloured simple graph corresponding to an externally prescribed symmetric latin rectangle \((R,(f,g))\) of odd order \(n\) on \(\Sigma\) is the edge-coloured simple graph \((G,(\Sigma,\psi))\) where \(V(G)=V(H)\cup\{v^{\lambda}\}\), \(E(G)=(E(H)\backslash L(H^{\star}))\cup\{v^{\lambda}v_i\,|\,i\in [r]\}\), \(\psi:E(G)\rightarrow\Sigma\) is defined by \(\psi(e)=\phi(e)\) if and only if \(e\in E(H)\backslash L(H^{\star})\), \(\psi(v^{\lambda}v_i)=\phi(v_iv_i)\) for all \(i\in [r]\) and \(\cH=(H,(C,\phi))\) is the proper \(\Sigma\)-edge-coloured \(r\)-free-type graph corresponding to an externally prescribed \(r\times r\) symmetric latin rectangle \((R,(f,g))\) of odd order \(n\).

\[lem1860\] The edge-coloured simple graph corresponding to an externally prescribed \(r\times r\) symmetric latin rectangle \((R,(f,g))\) of odd order \(n\) on \(\Sigma\) is a uniquely defined proper \(\Sigma\)-edge-coloured \(r\)-free-type simple graph of order \(n\).

If \(\cG\) is the proper \(\Sigma\)-edge-coloured simple graph corresponding to \((R,(f,g))\) then, by definition, \(V(G)=V(H)\cup\{v^{\lambda}\}\), where \(\cH=(H,(C\,phi))\) is the proper \(\Sigma\)-edge-coloured \(r\)-free-type graph corresponding to \((R,(f,g))\). Therefore, \(\cG\) is uniquely defined because \(\cH\), by Lemma \[lem\] is uniquely defined.

\(G\) is simple because \(e\in E(G)\) implies that either \(e\in E(H)\backslash L(H^{\star})\) or \(e\in\{v^{\lambda}v_i\,|\,i\in [r]\}\). Either way \(e\) is a non-loop edge.

\[lem1870\] An externally prescribed \(r\times r\) symmetric latin rectangle \((R,(f,g))\) of odd order \(n\) can be embedded in some symmetric latin square of order \(n\) if and only if the corresponding proper edge-coloured \(r\)-free-type simple graph of order \(n\) can be embedded in some proper \(\Sigma\)-edge-coloured complete simple graph of order \(n\).

If \(\cH\) is the corresponding proper \(\Sigma\)-edge-coloured \(r\)-free-type simple graph and \(\cH\) can be embedded in a proper \(\Sigma\)-edge-coloured complete simple graph \(\cK\) of order \(n\) then the symmetric latin square corresponding to \(\cK\) is a symmetric latin square of order \(n\) on \(\Sigma\) in which \(R\) is \((f,g)\)-embedded.

Conversely, is \(R\) can be \((f,g)\)-embedded in a symmetric latin square \(L\) of order \(n\) on \(\Sigma\) then the proper \(\Sigma\)-edge-coloured complete simple graph corresponding to \(L\) is a proper \(\Sigma\)-edge-coloured complete simple graph of order \(n\) in which \(\cH\) is embedded.

Lemma \[lem1870\] makes it natural to ask for a characterisation of those \((n-1)\)-edge-coloured \(r\)-free-type simple graphs of even order \(n\) which can be embedded in some \((n-1)\)-edge-coloured complete simple graph of order \(n\). Furthermore, despite it being a question of less obvious application to the problem of embedding symmetric latin rectangles, it is now also of interest to ask for a characterisation of those \(n\)-edge-coloured \(r\)-free-type simple graphs of odd order \(n\) which can be embedded in some complete simple graph of order \(n\). An obvious necessary condition for both of these problems is the relevant Ryser-type condition.

\[defn1880\] If \(\cH=(H,(C,\phi))\) is a proper \(C\)-edge-coloured \(r\)-free-type graph then \(\ek=|\{e\in E(H^{\star})\,|\,\phi(e)=c_k\}|\) and \(\Ek=\{e\in F\,|\,\phi(e)=c_k\}\).

\[def1890\] If \(\cH\) is a \(C_{[n-1]}\)-edge-coloured \(r\)-free-type simple graph of even order \(n\) then \(\cH\) is Ryser if and only if (\[def18901\]) holds for all \(c_k\in C_{[n-1]}\).

1. \(\ek\geq r-n/2+\Ek\) \[def18901\]

\[def1900\] If \(\cH\) is a \(C_{[n]}\)-edge-coloured \(r\)-free-type simple graph of odd order \(n\) then \(\cH\) is Ryser if and only if (\[def19001\]) holds for all \(c_k\in C_{[n]}\).

1. \(\ek\geq r-(n+1)/2+\Ek\) \[def19001\]

\[lem1905\] A proper \(C_{[n]}\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of order \(n\) can be embedded in a proper \(C_{[n]}\)-edge-coloured complete simple graph of order \(n\) only if \(\cH\) is Ryser.

If \(n\) is odd it turns out, remarkably, that being Ryser is sufficient.

\[Andersen and Hilton @MR92d:05061\] \[thm1910\] A proper \(C_{[n]}\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of odd order \(n\) can be embedded in a proper \(C_{[n]}\)-edge-coloured complete simple graph of order \(n\) if and only if \(\cH\) is Ryser.

Unfortunately, if \(n\) is even then the condition of being Ryser is no longer sufficient. A class of \((n-1)\)-edge-coloured \(r\)-free-type simple graphs of even order \(n\) which cannot be embedded in some \((n-1)\)-edge-coloured complete simple graph of order \(n\) was identified by Dugdale and Hilton. This class is characterised by the existence of a bad set of colours.

\[def1920\] A subset \(S\subset C_{[n-1]}\) is -bad if and only if (\[def19201\])-(\[def19203\]) hold, where \(N(S)\) denotes the set of all vertices of \(H^{\star}\) which are not the end edge of some edge of every colour \(c_k\in S\).

1. \(\eps(S)=(n-r-2)/2\) \[def19201\]

2. \(r|S|-2e(S)=(n-r)(|S|-1)\)\[def19202\]

3. \(|N(S)|=|S|-1\)\[def19203\]

It was conjecture by Dugdale and Hilton that a proper \(C_{[n-1]}\)-edge-coloured \(r\)-free-type simple graph \(\cH\) of even order \(n\) can be embedded in a proper \(C_{[n-1]}\)-edge-coloured complete simple graph of order \(n\) if and only if \(\cH\) is Ryser and \(C_{[n-1]}\) contains no \((n,r)\)-bad subset. In his thesis Allen (1996) Allen tackled this conjecture and proved the following related theorem.

\[Allen @SMA\] \[thm1930\] A proper \(C_{[n-1]}\)-edge-coloured complete simple graph \(\cH\) of even order \(n\) can be embedded in a proper \(C_{[n-1]}\)-edge-coloured complete graph of order \(n\) if \(\cH\) is Ryser and \(\Ek\geq 2\) or \(\Ek=0\) for all \(c_k\in C_{[n-1]}\).

In the next chapter the conjecture of Dugdale and Hilton is proved.

References

Allen, S. M. 1996. “Extending Edge-Colourings of Graphs.” PhD thesis, University of Reading.