\documentclass[12pt]{article} \usepackage{e-jc} \specs{P23}{20(3)}{2013} \sloppy \usepackage{amsthm,amsmath,amssymb} \allowdisplaybreaks \usepackage{graphicx} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{amsfonts} \usepackage {graphics} %\usepackage {pstcol} \usepackage {pstricks,pst-node,pst-coil} \setcounter{MaxMatrixCols}{10} %%%%%%%%%% \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%% %\newtheorem{acknowledgement}{Acknowledgement} %\newtheorem{algorithm}{Algorithm} %\newtheorem{axiom}{Axiom} %\newtheorem{case}{Case} %\newtheorem{claim}{Claim} %\newtheorem{conclusion}{Conclusion} %\newtheorem{condition}{Condition} %\newtheorem{conjecture}{Conjecture} %\newtheorem{criterion}{Criterion} %\newtheorem{definition}{Definition} %\newtheorem{example}{Example} %\newtheorem{exercise}{Exercise} %\newtheorem{lemma}{Lemma} %\newtheorem{notation}{Notation} %\newtheorem{problem}{Problem} %\newtheorem{proposition}{Proposition} %\newtheorem{remark}{Remark} %\newtheorem{solution}{Solution} %\newtheorem{summary}{Summary} %\newtheorem{theorem}{Theorem} %\numberwithin{equation}{section} %\newcommand{\cbdo}{\hfill \rule{.1in}{.1in}} %\newcommand{\prf}{\noindent{\bf Proof.~}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\input{tcilatex} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Can colour-blind distinguish colour palettes?} %\begin{document} %\title{Can colour-blind distinguish colour palettes?} \author{Rafa{\l} Kalinowski \qquad Monika Pil\'sniak\\ \and Jakub Przyby{\l}o\thanks{partly supported by the National Science Centre grant no. DEC-2011/01/D/ST1/04154.} \qquad Mariusz Wo\'zniak\\ \small AGH University of Science and Technology\\[-0.8ex] \small Krakow, Poland \\ \small\tt przybylo@wms.mat.agh.edu.pl\\ \small\tt \{kalinows,pilsniak,mwozniak\}@agh.edu.pl } %\thanks{Research partly supported by the Polish Ministry of Science and Higher Education.} \date{\dateline{May 6, 2012}{Aug 15, 2013}{Aug 23, 2013}\\ \small Mathematics Subject Classifications: 05C15} \begin{document} \maketitle \begin{abstract} Let $c:E(G)\rightarrow [k]$ be a colouring, not necessarily proper, of edges of a graph $G$. For a vertex $v\in V$, let $\overline{c}(v)=(a_1,\ldots,a_k)$, where $ a_i =|\{u:uv\in E(G),\;c(uv)=i\}|$, for $i\in [k].$ If we re-order the sequence $\overline{c}(v)$ non-decreasingly, we obtain a sequence $c^*(v)=(d_1,\ldots,d_k)$, called a {\it palette} of a vertex $v$. This can be viewed as the most comprehensive information about colours incident with $v$ which can be delivered by a person who is unable to name colours but distinguishes one from another. The smallest $k$ for which there exists a $c$ such that $c^*$ is a proper colouring of vertices of $G$ is called the {\it colour-blind index} of a graph $G$, and is denoted by ${\rm dal}(G).$ We conjecture that there is a constant $K$ such that ${\rm dal}(G)\leq K$ for every graph $G$ for which the parameter is well defined. As our main result we prove that $K\leq 6$ for regular graphs of sufficiently large degree, and for irregular graphs with $\delta (G)$ and $\Delta(G)$ satisfying certain conditions. The proofs are based on the Lopsided Lov\'asz Local Lemma. We also show that $K=3$ for all regular bipartite graphs, and for complete graphs of order $n\geq 8$. % keywords are optional \bigskip\noindent \textbf{Keywords:} graph colouring, distinguishing adjacent vertices, Lov\'asz Local Lemma \end{abstract} \section{Introduction} We use standard terminology and notation of graph theory. The set $\{1,\ldots,k\}$ of $k$ smallest positive integers is denoted by $[k].$ Given a simple graph $G=(V,E)$, let $c:E\rightarrow[k]$ be an egde-colouring, not necessarily proper. For a vertex $v\in V$, let $\overline{c}(v)=(a_1,\ldots,a_k)$, where $ a_i =|\{u:uv\in E(G),\;c(uv)=i\}|$, for $i\in [k].$ If $\overline{c}$ is a proper colouring of vertices of $G$, then $c$ {\it distinguishes neighbours by multisets}, and the smallest possible $k$ for which such $c$ exists is denoted by ${\rm ndi_m}(G)$. Clearly, if a graph $G$ contains $K_2$ as a component, then such a colouring does not exist. Karo\'nski, {\L}uczak and Thomason proved the following upper bound. \begin{theorem}\cite{KLT} For every graph $G$ without $K_2$ as a component, $${\rm ndi_m}\,(G)\leq 183.$$ \end{theorem} This was considerably improved by Addario-Berry et al. \begin{theorem}\cite{Louigi} For every graph $G$ without $K_2$ as a component, $${\rm ndi_m}\,( G)\leq 4.$$ Moreover, ${\rm ndi_m}(G)\leq 3$ if $\delta (G)\geq 1000.$ \end{theorem} %+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ \begin{figure}[htb] \centering \psset{unit=0.8cm} \begin{pspicture}(-2.2,-1)(2.2,1) \psset{radius=.1} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \dotnode(-2.2,-1){1} \dotnode(-2.2,1){2} \dotnode(-1,0){3} \dotnode(2.2,-1){6} \dotnode(2.2,1){5} \dotnode(1,0){4} \rput(-0.9,-0.4){(1,2)} \rput(0.9,-0.4){(1,2)} \ncline[linecolor=green]{1}{3} \ncline[linecolor=green]{2}{3} \ncline[linecolor=red]{3}{4} \ncline[linecolor=red]{4}{5} \ncline[linecolor=green]{4}{6} \end{pspicture} \caption{A colour-blind person could not distinguish the two vertices of degree three.}\label{przykl} \end{figure} %+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ In this paper, we introduce another type of distinguishing adjacent vertices by edge-colourings, as it would be done by a colour-blind person. If a colour-blind person looked at two green edges and one red, they would see two edges of the same colour and one of another colour. The same they would see if they looked at two red edges and one green (see Figure \ref{przykl}). If we re-order the sequence $\overline{c}(v)=(a_1,\ldots,a_k)$ non-decreasingly, we obtain a sequence $c^*(v)=(d_1,\ldots,d_k)$, called a {\it palette} of a vertex $v$. Note that there is a bijection between the set of all possible palettes of a vertex $v$ of degree $d$ and the set of all partitions of the integer $d$. We say that a {\it colour-blind person can distinguish neighbours} in a $k$-edge-colouring $c:E\rightarrow[k]$ if $c^*(u)\neq c^*(v)$ for every edge $uv\in E$, i.e., $c^*$ is a proper colouring of the vertices of $G$. The smallest possible number $k$ for which such colouring $c$ exists is called the {\it colour-blind index} of a graph $G$, and is denoted by ${\rm dal}(G)$. The notation chosen refers to the English chemist John Dalton, who in $1798$ wrote the first paper on colour-blindness. In fact, because of Dalton's work, the condition is often called \emph{daltonism}. It has to be noted that there are infinitely many graphs for which the colour-blind index is not defined, e.g., odd cycles (cp. Observation \ref{cycle}). All graphs with undefined colour-blind index, known to us, have minimum degree at most three. \begin{conjecture} There exists $\delta_0$ such that ${\rm dal}(G)$ is defined for every graph $G$ with $\delta(G)\geq \delta_0$. \end{conjecture} \begin{conjecture}\label{upper_bound_con} There exists a number $K$ such that ${\rm dal}(G)\leq K$ for every graph $G$ for which ${\rm dal}(G)$ exists. \end{conjecture} We prove Conjecture~\ref{upper_bound_con} for complete graphs, regular bipartite graphs, regular graphs of sufficiently large degree, and for irregular graphs with $\delta (G)$ and $\Delta(G)$ satisfying certain conditions (cp. Theorem~\ref{theorem-non-reg}). %=========================================================== \section{Results} \subsection{Complete graphs} Let $p(d)$ denote the number of partitions of an integer $d$, and let $p(d,k)$ be the number of partitions of $d$ into at most $k$ components. The following observation is obvious. \begin{observation}\label{pd} If $p(n-1)3$ and dal$(K_6)>3$ since $p(4,3)=4,p(5,3)=5$. Figure \ref{K5K7} shows that dal$(K_5)=4$. This colouring can be extended for $K_6$ by adding a new vertex and colouring blue all edges incident to it. The suitable colouring of $K_7$ with three colors is given in Figure \ref{K5K7}. %K8 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ \begin{figure}[htb] \centering \psset{unit=0.8cm} \begin{pspicture}(-5,-0.5)(1.5,5) \psset{radius=.1} % K8 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \dotnode(-4,1.4){1} \dotnode(-4,3.1){2} \dotnode(-2.6,4.5){3} \dotnode(-0.9,4.5){4} \dotnode(0.5,3.1){5} \dotnode(0.5,1.4){6} \dotnode(-0.9,0){7} \dotnode(-2.6,0){8} \rput(-4.8,1.4){({\red 0},{\blue 3},{\green 4})} \rput(-4.8,3.1){({\red 0},{\blue 0},{\green 7})} \rput(-2.9,5){({\red 2},{\blue 2},{\green 3})} \rput(-0.6,5){({\blue 0},{\red 1},{\green 6})} \rput(1.3,3.1){({\red 1},{\green 3},{\blue 3})} \rput(1.3,1.4){({\red 1},{\green 2},{\blue 4})} \rput(-0.6,-0.5){({\red 1},{\green 1},{\blue 5})} \rput(-2.9,-0.5){({\red 0},{\green 2},{\blue 5})} \ncline[linecolor=green]{1}{2} \ncline[linecolor=green]{1}{3} \ncline[linecolor=green]{1}{4} \ncline[linecolor=green]{1}{5} \ncline[linecolor=blue]{1}{6} \ncline[linecolor=blue]{1}{7} \ncline[linecolor=blue]{1}{8} \ncline[linecolor=green]{2}{3} \ncline[linecolor=green]{2}{4} \ncline[linecolor=green]{2}{5} \ncline[linecolor=green]{2}{6} \ncline[linecolor=green]{2}{7} \ncline[linecolor=green]{2}{8} \ncline[linecolor=green]{3}{4} \ncline[linecolor=red]{3}{5} \ncline[linecolor=red]{3}{6} \ncline[linecolor=blue]{3}{7} \ncline[linecolor=blue]{3}{8} \ncline[linecolor=green]{4}{5} \ncline[linecolor=green]{4}{6} \ncline[linecolor=red]{4}{7} \ncline[linecolor=green]{4}{8} \ncline[linecolor=blue]{5}{6} \ncline[linecolor=blue]{5}{7} \ncline[linecolor=blue]{5}{8} \ncline[linecolor=blue]{6}{7} \ncline[linecolor=blue]{6}{8} \ncline[linecolor=blue]{7}{8} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{pspicture} \caption{A colouring of $K_{8}$ with three colours.}\label{K8} \end{figure} To prove the claim for $n\geq 8$, we will show that for every $s\geq 4$, there exists an edge-colouring of $K_{2s}$ with three colours such that a colour-blind person can distinguish neighbours, and the vertex set can be partitioned into two subsets of equal size: a set $A$ comprised of $s$ vertices with the number of green incident edges greater than the numbers of blue and red ones (including a vertex $v_0$ having two blue incident edges and almost the same number of red and green ones, i.e., exactly $s-2$ and $s-1$, resp.), and a set $B$ comprised of $s-1$ vertices with the number of blue edges greater than the numbers of green and red ones, and a special vertex with a palette $(1,s-1,s-1)$ where 1 is the number of red edges. Such edge-colouring of $K_{8}$ is presented in Figure \ref{K8}. For the induction step, we first add a new vertex $u$ and colour every new edge $uv$ according to the following rule: $uv$ is coloured green for $v\in A$, and $uv$ is blue for $v\in B$. Note that this way we increase only the quantity of the most frequent colour for every vertex, increasing nothing but the last element of its corresponding partition of $2s$. Thus, we obtain an edge-colouring $c$ of $K_{2s+1}$ such that a colour-blind person can distinguish neighbours, and $c^*(u)=(0,s,s)$. To obtain a required colouring of $K_{2s+2}$, we again add a new vertex $u'$, and we colour every new edge $u'v$ as follows: $u'v$ is green for $v\in A\cup \{u\}\setminus\{v_0\}$, $u'v$ is blue for $v\in B$, and $u'v_0$ is red. Proceeding as before one may verify that this colouring of $K_{2s+2}$ meets our requirements (with $v_0$ playing the same role and $u'$ taking the role of a special vertex of $B$ in the subsequent induction step). \end{proof} \subsection{Regular bipartite graphs} \begin {observation}\label{cycle} The colour-blind index of any odd cycle is undefined. For even cycles, $${\rm dal} (C_n)\;=\;\left\{ \begin{array}{cl} 2 & {\rm if} \quad n\equiv 0\; ({\rm mod}\; 4),\\ 3 & {\rm if} \quad n\equiv 2\; ({\rm mod}\; 4). \end{array}\right.$$ \end{observation} \begin{proof} There are only two partitions of 2, the degree of vertices in a cycle: $(0,2)$ and $(1,1)$. Hence for odd $n$, dal$(C_n)$ is undefined since odd cycles are not 2-colourable. For even $n$, consecutive vertices on a cycle have to have palettes $(0,2)$ and $(1,1)$ alternately. Thus, each edge has to have one adjacent edge with the same colour and one with a different colour. Hence, we need a third colour for $n\equiv 2\; ({\rm mod}\; 4)$. \end{proof} \begin {theorem}\label{bip} For every $d$-regular bipartite graph $G$ with $d\geq 2$, $${\rm dal} (G)\leq 3.$$ \end{theorem} \begin{proof} We prove the following statement by induction on $d$: every $d$-regular bipartite graph with a bipartition $V(G)=A\cup B$ admits a colouring $c$ of edges with at most three colours such that $c^*(u)=(0,\ldots,0,d)$ if and only if $u\in A$. As seen in the proof of Observation \ref{cycle}, the claim holds for every connected component of a~2-regular bipartite graph $G$, hence it also holds for $G$. Let $d\geq 3$ and let $G$ be a $d$-regular bipartite graph with a bipartition $V(G)=A\cup B$. Consider a partial graph $G'=G-M=(V(G),E(G)\smallsetminus E(M))$, where $M$ is a perfect matching of $G$ (it exists since bipartite graphs are Class 1 and $G$ is regular). By the induction hypothesis, $G'$ has a colouring of edges such that, for every vertex $u\in A$, all edges incident with $u$ are of the same colour, say $c_u$. Now it suffices to colour each edge $e=uv\in M$, where $u\in A$, with the colour $c_u$. \end{proof} \subsection{Main results} \begin{theorem}\label{theorem-reg} For every $d$-regular graph $G$ of degree $d\geq 2\cdot 10^7$, $${\rm dal}(G)\leq 6.$$ \end{theorem} \begin{theorem}\label{theorem-non-reg} For every $R>1$, there exists $\delta_0$ such that if $G$ is any graph with minimum degree $\delta(G)\geq \delta_0$ and maximum degree $\Delta(G)\leq R\delta(G)$, then $${\rm dal}(G)\leq 6.$$ \end{theorem} \section{Proofs of Theorems~\ref{theorem-reg} and~\ref{theorem-non-reg}} \subsection{The Local Lemma} To prove Theorems~\ref{theorem-reg} and~\ref{theorem-non-reg} we shall use the following variation of the Lov\'asz Local Lemma, due to Erd\H os and Spencer~\cite{ErdosSpencerLL}, sometimes referred to as the `Lopsided' Local Lemma. Below we recall both its symmetric and general versions from Alon and Spencer~\cite{AlonSpencer} (Lemma 5.1.1, Corollary 5.1.2 and the comments below), the first of which is more convenient for proving Theorem~\ref{theorem-reg}. Given any digraph $D$ and its vertex $v$, by $N^+(v)$ we shall denote the out-neighbourhood of $v$ in $D$. \begin{theorem}[\textbf{Lopsided Symmetric Local Lemma}]\label{LLL-symmetric} Let $\mathcal{A}$ be a family of (typically bad) events in any probability space and let $D=(\mathcal{A},E)$ be a directed graph with maximum out-degree $\Delta^+$. Suppose that for each $A\in\mathcal{A}$ and every $\mathcal{C}\subset \mathcal{A}\smallsetminus N^+(A)$, \begin{equation}\label{EqLLL-symmetric_pr} {\rm Pr}\left(A|\bigcap_{C\in\mathcal{C}}\overline{C}\right) \leq p, \end{equation} where \begin{equation}\label{EqLLL-symmetric_e} ep(\Delta^++1)\leq 1. \end{equation} Then $ {\rm Pr}(\bigcap_{A\in\mathcal{A}}\overline{A})>0$. \end{theorem} \begin{theorem}[\textbf{Lopsided General Local Lemma}]\label{LLL-general} Let $\mathcal{A}$ be a family of (typically bad) events in any probability space and let $D=(\mathcal{A},E)$ be a directed graph. Suppose that there are real numbers $x_A\in [0,1)$ ($A\in\mathcal{A}$) such that, for each $A\in\mathcal{A}$ and every $\mathcal{C}\subset \mathcal{A}\smallsetminus N^+(A)$, \begin{equation}\label{EqLLL-general} {\rm Pr}\left(A|\bigcap_{C\in\mathcal{C}}\overline{C}\right) \leq x_A \prod_{B\leftarrow A} (1-x_B). \end{equation} Then $ {\rm Pr}(\bigcap_{A\in\mathcal{A}}\overline{A})\geq \prod_{A\in\mathcal{A}}(1-x_A)>0$. \end{theorem} Here $B\leftarrow A$ (or $A\rightarrow B$) means that there is an arc from $A$ to $B$ in $D$, so called \emph{lopsidependency graph}. We use this nonstandard notation to avoid confusion with arcs in a different directed graph introduced in our construction below. Note that we may assume that $A\notin \mathcal{C}$, since otherwise inequalities~(\ref{EqLLL-general}) and~(\ref{EqLLL-symmetric_pr}) trivially hold (for every non-negative $p$). \subsection{Random process} Suppose now we are given a set $\{1,2,\ldots,k\}$ of available colours, and for each edge $e$ of our graph $G=(V,E)$ we independently choose an element of this set randomly and equiprobably, and denote it by $c(e)$. By a \emph{bad event} $A_{uv}$ in such random process we shall mean obtaining $c^*(u)= c^*(v)$ for some edge $uv\in E$. It seems a natural approach to apply the Local Lemma in order to prove that the probability of choosing a colouring for which no bad event occurs is then positive. Note that the colouring generated by such random process is determined by the outcomes for a set of independent random variables $(X_e)_{e\in E}$, each associated with a single edge $e\in E$, and taking one of the values $1,2,\ldots,k$ with probability $1/k$. Thus our approach for colouring $G$ might be identified with a product probability space in which the probability of choosing a given edge colouring equals $1/k^{|E|}$. \subsection{Probability of a single bad event} Let $S_v$ denote the set of edges incident with a vertex $v\in V$, and for a given edge $uv\in E$, denote $S_{uv}:=S_u\cup S_v$. Note that for a given edge $e$, the event $A_e$ (that the colour palettes on the ends of $e$ are not distinguishable for a colour-blind person) depends only on the values of the random variables $X_f$ with $f\in S_e$. Suppose now that $k=6$, hence we are picking out edge colours from the set $[6]=\{1,2,\ldots,6\}$. Consider any fixed colouring of the edges in $S_u$, where $u$ is a vertex of $G$ with $d(u)=d$. Thus we are given a fixed partition $c^*=(d_1,d_2,\ldots,d_6)$ of $d$ such that $c^*(u)=c^*$. Let $v$ be a neighbour of $u$ with $d(v)=d$, and suppose that the colours of all edges incident with $v$, except for $uv$, are yet to be chosen randomly and independently. Let us estimate the probability of a bad event of obtaining $c^*(v)=c^*$. First note that the colour of $uv$ is irrelevant for the probability of distinguishing $u$ from $v$ in our circumstances (since a colour-blind person cannot ``name'' a given colour). In other words, ${\rm Pr}(c^*(v)=c^*|c(uv)=i)= {\rm Pr}(c^*(v)=c^*)$ for $i=1,2,\ldots,6$. Thus it will be sufficient to bound the latter of these probabilities for our purposes. Note then that: \begin{equation}\label{bound_sing_pr} {\rm Pr}(c^*(v)=c^*) \leq {d\choose{d_1,\ldots,d_6}}6!\frac{1}{6^d}, \end{equation} where the factor $6!$ is generated by the fact that we do not distinguish between a situation in which, e.g., colour $1$ appears $d_1$ times and colour $2$ appears $d_2$ times and the opposite, while ${d\choose{d_1,\ldots,d_6}}$ is just the number of distinct partitions of $d$ elements (edges) into six (enumerated) subsets $S_1,\ldots,S_6$ of cardinalities $d_1,\ldots,d_6$, resp., hence ${d\choose{d_1,\ldots,d_6}}=\frac{d!}{d_1!d_2!\cdots d_6!}$. Note that the factor ${d\choose{d_1,\ldots,d_6}}$ is maximized if $\max\{|d_i-d_j|\}\leq 1$, i.e., $d_1,\ldots,d_6$ are ``as equal as possible''. To see this, suppose that the opposite is true, i.e., $d_6\geq d_1+2$. Then ${d\choose{d_1+1,d_2,\ldots,d_5,d_6-1}} = \frac{d_6}{d_1+1} {d\choose{d_1,\ldots,d_6}}>{d\choose{d_1,\ldots,d_6}}$. Hence for $d\equiv r \pmod 6$, $r\in\{0,1,\ldots,5\}$, \begin{equation}\label{bound_max_multiset} \max {d\choose{d_1,\ldots,d_6}}=\frac{d!}{\left(\left(\frac{d-r}{6}\right)!\right)^{6-r}\left(\left(\frac{d+6-r}{6}\right)!\right)^{r}}, \end{equation} where the maximum is taken over all partitions $(d_1,\ldots,d_6)$ of $d$. \subsection{Lopsidependency graph} For the graph $G=(V,E)$, we construct our lopsidependency graph $D$ (which in fact is a digraph) as follows. Let its vertex set $\mathcal{A}$ consist of the bad events $A_{e}$ (with $e=uv\in E$ and $d(u)=d(v)$) that the ends of $e$ are not distinguishable for a colour-blind person. Note that no bad event is associated with an edge whose ends have distinct degrees. Further let us arbitrarily orient every edge of $G$. The resulting digraph will be denoted by $\overrightarrow{G}=(V,\overrightarrow{E})$. For every edge $e\in E$, we shall also denote its corresponding arc by $\overrightarrow{e}$. Then for every event $A_{e}$ with $\overrightarrow{e}=(u,v)\in \overrightarrow{E}$ we draw an arc from $A_{e}$ to every event $A_{e'}$ with $e'\in\bigcup_{f\in S_v\smallsetminus\{e\}} S_f$, $e'\neq e$ (i.e., $e'$ is any edge, $e'\neq e$, incident to some edge $f$, $f\neq e$, incident to $v$). \subsection{Conditional probability} Consider an event $A_{uv}$ with $\overrightarrow{uv} $ $=$ $(u,v)$ $\in$ $\overrightarrow{E}$, $d(u)=d(v)=d$, and any family of events $\mathcal{C}\subset \mathcal{A}\smallsetminus (N^+(A_{uv})\cup\{A_{uv}\})$. Note first that the event $\bigcup_{C\in\mathcal{C}}C$, hence also $\bigcap_{C\in\mathcal{C}}\overline{C}$, is determined by the values of the random variables $X_f$ with $f\in E_1:=\bigcup_{A_e\in\mathcal{C}}S_e$. Moreover, by the choice of arcs for our lopsidependency graph, none of the edges from $S_v$, except possibly $uv$, belongs to $E_1$. Let us denote $E=\{e_1,e_2,\ldots,e_m\}$ with $S_v=\{e_1,e_2,\ldots,e_d\}$ and $e_d=uv$. Let $S$ be a set of all (partial) colourings of the edges from $\{e_d,\ldots,e_m\}$ for which $\bigcap_{C\in\mathcal{C}}\overline{C}$ holds, i.e., the set of vectors $\widetilde{c}=(c_d,\ldots,c_m)\in [6]^{m-d+1}$ such that $(X_{e_d},\ldots,X_{e_m})=\widetilde{c}$ guarantees $\bigcap_{C\in\mathcal{C}}\overline{C}$. Then (if ${\rm Pr}(\bigcap_{C\in\mathcal{C}}\overline{C})>0$), \begin{eqnarray*} &&{\rm Pr}\left(A_{uv}|\bigcap_{C\in\mathcal{C}}\overline{C}\right)\\ &=& \frac{ {\rm Pr}(A_{uv}\cap\bigcap_{C\in\mathcal{C}}\overline{C})}{ {\rm Pr}(\bigcap_{C\in\mathcal{C}}\overline{C})}\\ &=& \frac{\sum_{\widetilde{c}\in S} {\rm Pr}(A_{uv}|(X_{e_d},\ldots,X_{e_m}) =\widetilde{c}) {\rm Pr}((X_{e_d},\ldots,X_{e_m})=\widetilde{c})}{ {\rm Pr}(\bigcap_{C\in\mathcal{C}}\overline{C})}\\ &\leq& \max_{\widetilde{c}\in S} {\rm Pr}(A_{uv}|(X_{e_d},\ldots,X_{e_m}) =\widetilde{c}) \sum_{\widetilde{c}\in S}\frac{ {\rm Pr}((X_{e_d},\ldots,X_{e_m})=\widetilde{c})}{ {\rm Pr}(\bigcap_{C\in\mathcal{C}}\overline{C})}\\ &=&\max_{\widetilde{c}\in S} {\rm Pr}(A_{uv}|(X_{e_d},\ldots,X_{e_m})=\widetilde{c})\\ &\leq& \max_{\widetilde{c}\in [6]^{m-d+1}} {\rm Pr}(A_{uv}|(X_{e_d},\ldots,X_{e_m})=\widetilde{c}).\\ \end{eqnarray*} Hence by~(\ref{bound_sing_pr}) and~(\ref{bound_max_multiset}), for $d\equiv r \pmod 6$, $r\in\{0,1,\ldots,5\}$, we have \begin{equation}\label{bound_cond_prob} {\rm Pr}\left(A_{uv}|\bigcap_{C\in\mathcal{C}}\overline{C}\right) \leq \frac{d!}{\left(\left(\frac{d-r}{6}\right)!\right)^{6-r}\left(\left(\frac{d+6-r}{6}\right)!\right)^{r}}6!\frac{1}{6^d}.\\ \end{equation} \subsection{Regular graphs} Assume that $G$ is a regular graph of degree $d\equiv r \pmod 6$, $r\in\{0,1,\ldots,5\}$, where $d\geq 2\cdot 10^7$. For every $A\in \mathcal{A}$, the number of its outgoing arcs, $d^+(A)$, is then at most $(d-1)d\leq d^2-1$. Consider an event $A_{uv}\in \mathcal{A}$ with $\overrightarrow{uv}=(u,v)\in \overrightarrow{E}$ and any family of events $\mathcal{C}\subset \mathcal{A}\smallsetminus (N^+(A_{uv})\cup\{A_{uv}\})$. Then in order to prove the existence of a desired colouring, by Theorem~\ref{LLL-symmetric}, it is sufficient to show that \begin{equation*}\label{EqForSLLL} d^2\cdot e\cdot {\rm Pr}\left(A_{uv}|\bigcap_{C\in\mathcal{C}}\overline{C}\right) \leq 1. \end{equation*} By inequality~(\ref{bound_cond_prob}), it is then enough to prove that \begin{equation*} a_d:=d^2\cdot e\cdot \frac{d!}{\left(\left(\frac{d-r}{6}\right)!\right)^{6-r}\left(\left(\frac{d+6-r}{6}\right)!\right)^{r}}6!\frac{1}{6^d} \leq 1. \end{equation*} We shall first show that the sequence $(a_d)_{d\geq 6\cdot 10^6}$ consists of six decreasing subsequences $(a_{6n+i})_{n\geq 10^6}$, $i= 0,1,\ldots,5$. For this purpose consider the following proportion: \begin{eqnarray*} \frac{a_{d}}{a_{d-6}} &=& \frac{d^2\cdot d!\left(\left(\frac{d-r}{6}-1\right)!\right)^{6-r}\left(\left(\frac{d+6-r}{6}-1\right)!\right)^{r}} {(d-6)^2\cdot (d-6)!\left(\left(\frac{d-r}{6}\right)!\right)^{6-r}\left(\left(\frac{d+6-r}{6}\right)!\right)^{r}6^6}\\ &=& \frac{d^2 d(d-1)(d-2)(d-3)(d-4)(d-5)}{(d-6)^2(d-r)^{6-r}(d+6-r)^r}\\ &=& \frac{d^8-15d^7+85d^6-225d^5+274d^4-120d^3}{d^8-12d^7+P_r(d)}, \end{eqnarray*} where $P_r(d)$ is a polynomial of degree (at most) six, and \begin{equation*} P_r(d)\geq -\sum_{j=2}^8 {8 \choose j}6^jd^{8-j} \geq -\sum_{j=2}^8 {8 \choose j}6^jd^{6}\geq -6\cdot 10^6d^6, \end{equation*} hence $$\frac{a_{d}}{a_{d-6}}\leq \frac{d^8-15d^7+d^7}{d^8-12d^7-d^7}<1$$ for $d\geq 6\cdot 10^6$. To prove that $a_d\leq 1$ for $d\geq 2\cdot 10^7$, it is then sufficient to compute $a_{20000000}=0.955248$, $a_{20000001}=0.955247$, $a_{20000002}=0.955247$, $a_{20000003}=0.955248$, $a_{20000004}=0.955248$ and $a_{20000005}=0.955247$ (in fact this sequence attains values below $1$ already from $d\approx 1.83\cdot 10^7$). Theorem~\ref{theorem-reg} follows then by Theorem~\ref{LLL-symmetric}. \subsection{Irregular graphs} Assume now that we are given a constant $R>1$ and a graph $G$ of maximum degree $\Delta \leq R\delta$. We shall prove that if its minimum degree $\delta$ is large enough, i.e., larger than some constant $\delta_0$, then the general version of the Lopsided Local Lemma implies a positive probability of choosing a desired edge colouring in our random process. We do not give an explicit formula for $\delta_0$, and only use the expression `for $\delta$ sufficiently large' when necessary. This can however be derived from the proof, and it surely grows along with $R$. Again consider an event $A_{uv}\in \mathcal{A}$ with $\overrightarrow{uv}=(u,v)\in \overrightarrow{E}$, $d(u)=d(v)=d\equiv r \pmod 6$, $r\in\{0,1,\ldots,5\}$ ($\Delta\geq d\geq\delta\geq\delta_0$), and any family of events $\mathcal{C}\subset \mathcal{A}\smallsetminus (N^+(A_{uv})\cup\{A_{uv}\})$. This time we shall use the Stirling formula: \begin{equation}\label{Stirling_form} n!=\left(\frac{n}{e}\right)^n\sqrt{2\pi n}e^{\alpha_n},~~ {\rm where}~~ \frac{1}{12n+1}<\alpha_n<\frac{1}{12n} \end{equation} to bound the right hand side of inequality~(\ref{bound_cond_prob}) on the conditional probability $ {\rm Pr}(A_{uv}|\bigcap_{C\in\mathcal{C}}\overline{C})$. By~(\ref{bound_cond_prob}) and~(\ref{Stirling_form}) we thus obtain: \begin{eqnarray*}&& {\rm Pr}\left(A_{uv}|\bigcap_{C\in\mathcal{C}}\overline{C}\right)\\ &\leq&\frac{\left(\frac{d}{e}\right)^d\sqrt{2\pi d}e^{\frac{1}{12d}}\cdot 6!\frac{1}{6^d}}{\left(\left(\frac{d-r}{6e}\right)^\frac{d-r}{6}\sqrt{2\pi \frac{d-r}{6}}e^{\frac{1}{ 2(d-r)+1}}\right)^{6-r}\left(\left(\frac{d+6-r}{6e}\right)^\frac{d+6-r}{6}\sqrt{2\pi \frac{d+6-r}{6}}e^{\frac{1}{ 2(d+6-r)+1}}\right)^{r}}\\ &\leq&\frac{\left(\frac{d}{e}\right)^d\sqrt{2\pi d}\cdot 6!}{\left(\left(\frac{d-r}{6e}\right)^\frac{d-r}{6}\sqrt{2\pi \frac{d-r}{6}}\right)^{6-r}\left(\left(\frac{d+6-r}{6e}\right)^\frac{d+6-r}{6}\sqrt{2\pi \frac{d+6-r}{6}}\right)^{r}6^d}\\ &=&\frac{\left(\frac{d}{e}\right)^d\sqrt{2\pi d}\cdot 6!}{\left(\left(\frac{d-r}{e}\right)^\frac{d-r}{6}\sqrt{\frac{2\pi}{6} (d-r)}\right)^{6-r}\left(\left(\frac{d+6-r}{e}\right)^\frac{d+6-r}{6}\sqrt{\frac{2\pi}{6}(d+6-r)}\right)^{r}}\\ &=&6!\sqrt{2\pi}\sqrt{\frac{d}{\left(\frac{2\pi}{6}\right)^6(d-r)^{6-r}(d+6-r)^r}}\left(\frac{d-r}{d}\right)^{-\frac{(d-r)(6-r)}{6}}\\ &&\times\left(\frac{d+6-r}{d}\right)^{-\frac{(d+6-r)r}{6}}\\ &=&6!\sqrt{2\pi}\sqrt{\frac{d}{\left(\frac{2\pi}{6}\right)^2(d^6-Q_4(d))}}\frac{6}{2\pi} \left[\left(1-\frac{r}{d}\right)^{-\frac{d}{r}}\right]^{\frac{r(d-r)(6-r)}{6d}}\\ &&\times\frac{6}{2\pi}\left[\left(1+\frac{6-r}{d}\right)^{\frac{d}{6-r}}\right]^{-\frac{(6-r)(d+6-r)r}{6d}},\\ \end{eqnarray*} where $Q_4(d)$ is a polynomial of degree (at most) four of a variable $d$ (and we must assume $r\neq 0$ for the last equality to hold), and $$\lim_{d\to\infty}\frac{6}{2\pi}\left[\left(1-\frac{r}{d}\right)^{-\frac{d}{r}}\right]^{\frac{r(d-r)(6-r)}{6d}} = \frac{6}{2\pi}e^{\frac{r(6-r)}{6}}\ln(1+t)$ for $t>-1$, $t\neq 0$, we have $$\ln\left(1-\frac{eb}{x^{\frac{5}{2}}}\right) +\frac{\frac{5}{2}\frac{eb}{x^{\frac{5}{2}}}}{1-\frac{eb}{x^{\frac{5}{2}}}}> \ln\left(1-\frac{eb}{x^{\frac{5}{2}}}\right) +\ln\left(1+\frac{\frac{5}{2}\frac{eb}{x^{\frac{5}{2}}}}{1-\frac{eb}{x^{\frac{5}{2}}}}\right) =\ln\left(1+\frac{3}{2}\frac{eb}{x^{\frac{5}{2}}}\right),$$ and thus $f'(x)>0$ for $x$ sufficiently large. Then if $\delta_0$ (thus also $\delta$) is sufficiently large, in particular $\delta_0\geq (3Rb)^2$, by~(\ref{product_ineq}) we obtain: \begin{eqnarray*} x_{A_{uv}} \prod_{B\leftarrow A_{uv}} (1-x_B) &>& \frac{eb}{d^{\frac{5}{2}}}\left(1-\frac{eb}{\delta^{\frac{5}{2}}}\right)^{\delta d} = \frac{eb}{d^{\frac{5}{2}}}\left[\left(1-\frac{eb}{\delta^{\frac{5}{2}}} \right)^{-\frac{\delta^{\frac{5}{2}}}{eb}}\right]^{-\frac{deb}{\delta^{\frac{3}{2}}}}\\ &\geq& \frac{eb}{d^{\frac{5}{2}}}\left[\left(1-\frac{eb}{\delta^{\frac{5}{2}}} \right)^{-\frac{\delta^{\frac{5}{2}}}{eb}}\right]^{-\frac{R\delta eb}{\delta^{\frac{3}{2}}}} \geq \frac{eb}{d^{\frac{5}{2}}}\left[\left(1-\frac{eb}{\delta^{\frac{5}{2}}} \right)^{-\frac{\delta^{\frac{5}{2}}}{eb}}\right]^{-\frac{R eb}{\delta_0^{\frac{1}{2}}}}\\ &\geq& \frac{eb}{d^{\frac{5}{2}}}\left[\left(1-\frac{eb}{\delta^{\frac{5}{2}}} \right)^{-\frac{\delta^{\frac{5}{2}}}{eb}}\right]^{-\frac{e}{3}} \geq \frac{eb}{d^{\frac{5}{2}}}e^{-1} \geq \frac{b}{d^{\frac{5}{2}}}\\ &\geq& {\rm Pr}\left(A_{uv}|\bigcap_{C\in\mathcal{C}}\overline{C}\right). \end{eqnarray*} Theorem~\ref{theorem-non-reg} follows then by Theorem~\ref{LLL-general}. \section{Concluding remarks} Note that by the proof above, $\delta_0$ tends to infinity while $R$ grows, in particular $\delta_0\geq (3Rb)^2$. Hence without bounding $\Delta/\delta$, we are unable to prove that six colours are sufficient in our random process. In fact asymptotic estimations imply that within this approach no constant (even large) number of available colours helps to avoid the assumption on $\Delta/\delta$. One of the interesting problems involved is here also the fact that, unlike in many other similar problems, increasing the number of colours, at some point (quite fast) starts increasing the probability of a bad event to appear too. To see this, consider, e.g., a situation when the number of available colours is larger than $\Delta$. Then there is ``a reasonable'' chance that all edges incident with a given vertex $u$ have pairwise distinct colours, and this probability grows with the number of admitted colours. Thus the probability that some neighbour $v$ of $u$ of the same degree meets the set of pairwise distinct colours is also relatively big. These would be indistinguishable for a colour-blind person then. \begin{thebibliography}{99} \bibitem{FGH} J.~Fisher, R.~L. Graham, and F.~Harary. \newblock A simpler counterexample to the reconstruction conjecture for denumerable graphs. \newblock {\em J. Combin. Theory Ser. B}, 12:203--204, 1972. \bibitem{Louigi} L.~Addario-Berry, R.E.L.~Aldred, K.~Dalal, B.A.~Reed. \newblock Vertex colouring edge partitions. \newblock {\em J. Combin. Theory Ser. B}, 94:237--244, 2005. \bibitem{AlonSpencer} N.~Alon, J.H.~Spencer. \newblock {\em The Probabilistic Method}, 2nd edition, Wiley, New York, 2000. \bibitem{ErdosSpencerLL} P.~Erd\H os, J.~Spencer. \newblock Lopsided Lov\'asz Local Lemma and Latin transversals. \newblock {\em Discrete Appl. Math.}, 30:151--154, 1991. \bibitem{KLT} M.~Karo\'nski, T.~{\L}uczak, A.~Thomason. \newblock Edge weights and vertex colours. \newblock {\em J. Combin. Theory Ser. B}, 91:151--157, 2004. \end{thebibliography} \end{document}