% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P2.19}{21(2)}{2014} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Colour-blind can distinguish colour pallets} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Jakub Przyby{\l}o\thanks{Research partly supported by the Polish Ministry of Science and Higher Education and supported by the National Science Centre grant no. DEC-2011/01/D/ST1/04154.}\\ \small AGH University of Science and Technology\\[-0.8ex] \small al. A. Mickiewicza 30\\[-0.8ex] \small 30-059 Krakow, Poland\\ \small\tt przybylo@wms.mat.agh.edu.pl } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Sep 24, 2013}{Apr 3, 2014}{May 2, 2014}\\ \small Mathematics Subject Classifications: 05C15} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Let $c:E\to\{1,\ldots,k\}$ be an edge colouring of a connected graph $G=(V,E)$. Each vertex $v$ is endowed with a naturally defined pallet under $c$, understood as the multiset of colours incident with $v$. If $\delta(G)\geq 2$, we obviously (for $k$ large enough) may colour the edges of $G$ so that adjacent vertices are distinguished by their pallets of colours. Suppose then that our coloured graph is examined by a person who is unable to name colours, but perceives if two object placed next to each other are coloured differently. Can we colour $G$ so that this individual can distinguish colour pallets of adjacent vertices? It is proved that if $\delta(G)$ is large enough, then it is possible using just colours 1, 2 and 3. This result is sharp and improves all earlier ones. It also constitutes a strengthening of a result by %Addario-Berry, Aldred, Dalal and Reed [J. Combin. Theory Ser. B 94 (2005) 237--244]. Addario-Berry, Aldred, Dalal and Reed (2005). % keywords are optional \bigskip\noindent \textbf{Keywords:} Neighbour distinguishing colouring; Colour pallet; Colour-blind. \end{abstract} \section{Results} Consider a simple graph $G=(V,E)$. Given vertex $v\in V$, we denote by $d(v)$ the \emph{degree} of $v$, and by $N(v)$ the \emph{neighbourhood} of $v$ in $G$. To be precise, we shall also use the notation $d_G(v)$ and $N_G(v)$, resp., at times. A not necessarily proper edge colouring $c:E\to\{1,2,\ldots,k\}$ is called \emph{neighbour distinguishing} (or \emph{vertex colouring}, see e.g.~\cite{Louigi2}) if for every edge $uv\in E$, the multiset of colours incident with $u$ is distinct from the multiset of colours incident with $v$. The problem of finding minimum $k$ so that every graph without a $K_2$ component admits a neighbour distinguishing edge colouring with $k$ colours first arose in the paper of Karo\'nski, {\L}uczak and Thomason \cite{123KLT} as a tool developed for making some progress concerning now well known 1-2-3 Conjecture, cf. \cite{KalKarPf_123} for the most recent result regarding this. They proved that $k\leq 183$ always suffice, or even $k\leq 30$ if the minimum degree $\delta$ of $G$ is at least $10^{99}$. This was then greatly improved by Addario-Berry et al.~\cite{Louigi2}, who showed that four colours are sufficient and provided the following refinement for graphs of sufficiently large minimum degree. \begin{theorem} \emph{(\cite{Louigi2})} \label{Louigi_Th_multisets_3} Every graph of minimum degree $\delta\geq 1000$ and without a $K_2$ component admits a neighbour distinguishing colouring with $1$, $2$ and $3$. \end{theorem} For every vertex $v$ and a colouring $c:E\to \{1,2,\ldots,k\}$, set $\overline{c}(v)=(a_1,\ldots,a_k)$, where $a_i=|c^{-1}(\{i\})|$ for $i=1,\ldots,k$. Thus $c$ is neighbour distinguishing if $\overline{c}(u)$ and $\overline{c}(v)$ differ in at least one coordinate for every edge $uv\in E$. Let us strengthen this requirement as follows: For every $v$, let us re-order $\overline{c}(v)$ non-decreasingly and denote the outcome by $c^*(v)=(d_1,\ldots,d_k)$, hence $0\leq d_1\leq d_2\leq \ldots \leq d_k$ and $\sum_{i=1}^kd_i=d(v)$. We say that a \emph{colour-blind person can distinguish neighbours} under colouring $c$ if for every edge $uv\in E$, $c^*(u)\neq c^*(v)$ (hence also $\overline{c}(u)\neq\overline{c}(v)$). Here we consider a peculiar kind of colour-blindness a person suffering from which cannot name colours, but is able to state whether two objects (e.g. edges) placed next to each other are coloured the same or differently. Therefore they are able to group and count subsets of monocoloured edges incident with $v$, but cannot associate these quantities to the specific colours, and thus $c^*(v)$ represents the most comprehensive information they can deliver on the frequencies of colours surrounding $v$. The smallest integer $k$ for which such colouring exists is called the \emph{colour-blind index} of $G$, and is denoted by ${\rm dal}(G)$. This notion 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}. There are graphs for which this parameter is not defined. All known examples of such graphs have minimum degree at most $3$. It is thus believed that the following conjecture should hold with $\delta_0=4$. \begin{conjecture}\emph{(\cite{daltonisci})} \label{MinDeg_Con} There exists $\delta_0$ such that ${\rm dal}(G)$ is defined for every graph $G$ with $\delta(G)\geq \delta_0$. \end{conjecture} Moreover, it has been conjectured and proven the following. \begin{conjecture}\emph{(\cite{daltonisci})} \label{upper_bound_con} There exists a constant $K$ such that ${\rm dal}(G)\leq K$ for every graph $G$ for which ${\rm dal}(G)$ exists. \end{conjecture} \begin{theorem}\emph{(\cite{daltonisci})} \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} \begin{theorem}\emph{(\cite{daltonisci})} \label{theorem-reg} For every $d$-regular graph $G$ of degree $d\geq 2\cdot 10^7$, $${\rm dal}(G)\leq 6.$$ \end{theorem} Following the probabilistic approach from~\cite{daltonisci}, Przyby{\l}o proved then that in the case of regular graphs one may significantly reduce the threshold for $d$ at the cost of a few more colours. \begin{theorem}\emph{(\cite{daltonisci1500})} \label{main_theorem-reg} For every $d$-regular graph $G$ of degree $d\geq 960$, $${\rm dal}(G)\leq 15.$$ \end{theorem} In this note we shall prove the following improvement of Theorems~\ref{theorem-non-reg}, \ref{theorem-reg} and \ref{main_theorem-reg}, which is a strengthening of Theorem~\ref{Louigi_Th_multisets_3} as well. Note that this also proves Conjecture~\ref{MinDeg_Con} to hold. \begin{theorem}\label{Main3Theorem} For each graph $G$ with $\delta(G)\geq 3462$, $${\rm dal}(G)\leq 3.$$ \end{theorem} Note that this upper bound is tight, since e.g. ${\rm dal}(K_n)=3$ for every $n\geq 7$, see~\cite{daltonisci} for details. \section{Proofs} We shall use the following theorem from \cite{Louigi}, which develops similar ideas included in \cite{Louigi2,Louigi30}. \begin{theorem} \emph{(\cite{Louigi})} \label{ADRTh} Given a graph $G=(V,E)$ and for every $v\in V$, integers $a^-_v,a^+_v$ such that $a^-_v\leqslant\big\lfloor\frac{d(v)}{2}\big\rfloor\leqslant a^+_v60$, there exist a list $I_d$ of at least $\frac{d-57}{4}$ consecutive integers and a divisible by $7$ integer $h_d$, $h_d>|I_d|$, such that for any graph $G=(V,E)$ with minimum degree $\delta >60$ and any list of integers $(a_v)_{v\in V}$ with $a_v\in I_{d(v)}$ for each $v\in V$, there exists a spanning subgraph $H$ of $G$ such that $d_H(v)\in\{a_v,a_v+1,a_v+h_{d(v)},a_v+h_{d(v)}+1\}$ for every $v\in V$. \end{corollary} \begin{proof} We shall prove that the lists $I_d:=\{\left\lceil\frac{d}{4}\right\rceil+3, \ldots, \left\lfloor\frac{d}{2}\right\rfloor-11\}$, where $$|I_d|=\left(\left\lfloor\frac{d}{2}\right\rfloor-11\right)-\left(\left\lceil\frac{d}{4}\right\rceil+3\right)+1 \geq \frac{d-57}{4},$$ and $h_d$ defined as the least integer divisible by $7$ not smaller than $\left\lceil\frac{d}{4}\right\rceil$ fulfill our requirements. It is then sufficient to prove that for a given vertex $v$ with $d(v)>60$, any pair of integers $a_v^-\in I_{d(v)}$ and $a_v^+:=a_v^-+h_{d(v)}$ comply with the requirements of Theorem~\ref{ADRTh}. For any such $a_v^-$ and $h_{d(v)}$ note first that by definition, $$\left\lceil\frac{d(v)}{4}\right\rceil\leq h_{d(v)}\leq \left\lceil\frac{d(v)}{4}\right\rceil+6.$$ Clearly $a_v^-\leq \left\lfloor\frac{d(v)}{2}\right\rfloor$ and $$\left\lfloor\frac{d(v)}{2}\right\rfloor \leq a_v^+=a_v^-+h_{d(v)} < d(v),$$ hence it is enough to prove inequality~(\ref{min}) for our $a_v^-$ and $a_v^+$. Note then that $$a_v^+=a_v^-+h_{d(v)}\leq a_v^-+\left\lceil\frac{d(v)}{4}\right\rceil+6 = a_v^-+\left(\left\lceil\frac{d(v)}{4}\right\rceil+3\right)+3 \leq 2a_v^-+3$$ and analogously, \begin{eqnarray*} a_v^+ & \leq & \frac{a_v^-}{2}+\frac{a_v^-}{2}+ \left\lceil\frac{d(v)}{4}\right\rceil + 5 + 1 \\ & \leq & \frac{a_v^-}{2}+ \left(\frac{\left\lfloor\frac{d(v)}{2}\right\rfloor-11}{2}+ \left\lceil\frac{d(v)}{4}\right\rceil + 5\right) + 1 \leq \frac{a_v^-}{2}+\frac{d(v)}{2}+1, \end{eqnarray*} thus (\ref{min}) holds. \end{proof} Note that the elements of each set $\{a_v,a_v+1,a_v+h_{d(v)},a_v+h_{d(v)}+1\}$ from the corollary above have only two (consecutive) remainders modulo $7$. \begin{observation}\label{Z7partition} For any $c\in \mathbb{Z}_7$ there exist $a,b\in\mathbb{Z}_7$ such that the sets $A:=\{a,a+1\}$, $B:=\{b,b+1\}$ and $C:=\{c-x-y:x\in A, y\in B\}$ (additions modulo $7$) form a partition of $\mathbb{Z}_7$. \end{observation} \begin{proof} Note that $C=\{c-a-b-2,c-a-b-1,c-a-b\}$. For every $c=3p+1$, $p\in \mathbb{Z}_7$, it is thus sufficient to take $a=p$ and $b=p+2$, since then $A=\{p,p+1\}$, $B=\{p+2,p+3\}$ and $C=\{p+4,p+5,p+6\}$ in $\mathbb{Z}_7$. \end{proof} Note also that the number $7$ cannot be replaced by a smaller integer in the observation above (if we require $A$, $B$ and $C$ to be disjoint).\\ %\textsc{Proof of Theorem~\ref{Main3Theorem}}. \begin{proof}[Proof of Theorem~\ref{Main3Theorem}] We shall colour our graph using the colours $1$, $2$ and $3$. First we shall choose edges to be coloured with $1$. These will form a subgraph $H_1$ of $G$. Then we shall choose some subgraph $H_2$ of the graph $G'=(V,E\smallsetminus E(H_1))$ obtained by removing the edges of $H_1$ from $G$, and colour the edges of $H_2$ with $2$. The remaining edges will receive colour $3$. Note that any two neighbours may not be distinguishable in the obtained colouring only if they share the same degree. For a given degree $d\geq 3462$ with remainder $c$ modulo $7$, let $\mathbb{Z}_7=A_d\cup B_d\cup C_d$ be a partition guaranteed by Observation~\ref{Z7partition}, and let $I_d$ be a set of integers from Corollary~\ref{QuarterLemma}, $|I_d|\geq \frac{d-57}{4}$. We shall ensure that the subgraphs $H_1$ and $H_2$ are chosen so that $d_{H_1}(v)\pmod 7$ belongs to $A_{d(v)}$, $d_{H_2}(v)\pmod 7$ belongs to $B_{d(v)}$, and hence $d(v)-d_{H_1}(v)-d_{H_2}(v)\pmod 7$ belongs to $C_{d(v)}$. Then two neighbours will not be distinguishable for a colour-blind person only if they have exactly the same number of incident edges in each of the colours. Let us fix any ordering of the vertices of $G$ into a sequence $v_1,v_2,\ldots, v_n$. One after another we shall choose $a_{v_i}$ for every $v_i$ in order to apply Corollary~\ref{QuarterLemma}. Suppose that $v_i$ ($1\leq i\leq n$) has degree $d$, $A_d=\{a,a+1\}$, and we have already chosen $a_{v_j}$ for each vertex $v_j$ with $j|I_{d}|$, then for a given vertex $v$ and its backward neighbour $w$, both of degree $d$, we may have $d_{H_1}(v)=d_{H_1}(w)$ only if $w\in B(v)$. Let us now consider the graph $G'$ that was left of $G$ after removing the edges of $H_1$. We may assume that we have used $I_d$ and $h_d$ defined in the first three lines of the proof of Corollary~\ref{QuarterLemma}, hence for each $v\in V$ of degree $d$ in $G$, $$d_{H_1}(v)\leq a_v+h_{d(v)}+1 \leq \left\lfloor\frac{d}{2}\right\rfloor-11 + \left\lceil\frac{d}{4}\right\rceil +6 +1= \left\lfloor\frac{d}{2}\right\rfloor + \left\lceil\frac{d}{4}\right\rceil -4 \leq \frac{3}{4}d-\frac{7}{2}.$$ Consequently, $$\delta(G')\geq \left\lceil\frac{1}{4}\delta(G)+\frac{7}{2}\right\rceil \geq 869.$$ In order to again apply Corollary~\ref{QuarterLemma}, this time to $G'$, one after another we choose $b_{v_i}$ for each vertex $v_i$ in the fixed ordering. Suppose that $v_i$ ($1\leq i\leq n$) had degree $d$ in $G$, $B_d=\{b,b+1\}$, and we have already chosen $b_{v_j}$ for each vertex $v_j$ with $j