% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}

% 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}{Mar 27, 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].

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:}  Neighbour distinguishing colouring; Colour pallet; Colour-blind person
\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^+_v<d(v)$ and
\begin{equation} \label{min}
a^+_v\leqslant\min\left\{\frac{d(v)+a^-_v}{2}+1,2a^-_v+3\right\},
\end{equation}
there exists a spanning subgraph $H$ of $G$ such that
$d_H(v)\in\{a^-_v,a^-_v+1,a^+_v,a^+_v+1\}$ for each $v\in V$.
\end{theorem}


\begin{corollary} \label{QuarterLemma}
For each integer $d$, $d>60$, 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$.
We then choose $a_{v_i}\in I_d$ greedily so that $a_{v_i}\equiv a\pmod 7$ and the number of \emph{backward neighbours} $v_j$ of $v_i$, i.e. $v_j\in N(v_i)$ with $j<i$, of degree $d$ and with $a_{v_j}=a_{v_i}$ is as small as possible. Denote this minimal subset of backward neighbours of $v_i$ by $B(v_i)$. In particular we may have $|B(v_i)|= 0$. Note that we have at least $\left\lfloor\frac{I_d}{7}\right\rfloor$ choices for $a_{v_i}$ in $I_d$ such that $a_{v_i}\equiv a \pmod 7$. Moreover
$$29\left\lfloor\frac{I_d}{7}\right\rfloor \geq 29\left\lfloor\frac{d-57}{28}\right\rfloor \geq 29\left(\frac{d-57}{28}-\frac{27}{28}\right) = d+1+\frac{d-2464}{28} \geq  d+1,$$
and thus by the pigeonhole principle, $a_{v_i}$ can be chosen so that $|B(v_i)\cup \{v_i\}|\leq 29$, hence $|B(v_i)|\leq 28$.
For $a_{v_1},\ldots, a_{v_n}$ chosen in this manner, Corollary~\ref{QuarterLemma} guarantees the existence of a subgraph $H_1$ of $G$ such that
$d_{H_1}(v)\in\{a_v,a_v+1,a_v+h_{d(v)},a_v+h_{d(v)}+1\}$ for each $v\in V$, where $h_{d(v)}$'s are the divisible by $7$ constants from Corollary~\ref{QuarterLemma}. Moreover, since for each $d$ we have $h_{d}>|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<i$.
Denote by $B'(v_i)$ the subset of those vertices $w$ from $B(v_i)$
for which $d_{H_1}(w)=d_{H_1}(v)$, hence $|B'(v_i)|\leq |B(v_i)|\leq 28$.
We then choose $b_{v_i}\in I_{d_{G'}(v_i)}$ greedily so that $b_{v_i}\equiv b\pmod 7$ and $b_{v_i}\neq b_{v_j}$ for each $v_j\in B'(v_i)$.
Since $|B'(v_i)|\leq 28$ and
$$|I_{d_{G'}(v_i)}|\geq \frac{d_{G'}(v_i)-57}{4}\geq \frac{869-57}{4}=29\cdot 7,$$
such choice is always possible. Then, by Corollary~\ref{QuarterLemma}, there exists a subgraph $H_2$ of $G'$ with
$d_{H_2}(v)\in\{b_v,b_v+1,b_v+h_{d_{G'}(v)},b_v+h_{d_{G'}(v)}+1\}$ for each vertex $v\in V$.
Note then that for every $v\in V$ and $w\in B'(v)$, $d_{G'}(v)=d_{G'}(w)$, and thus $d_{H_2}(v)\neq d_{H_2}(w)$.

As mentioned, we colour each edge of $H_1$ with $1$, each edge of $H_2$ with $2$, and the remaining edges receive colour $3$.
Additionally, by our construction, for every vertex $v\in V$ we have $d_{H_1}(v)\pmod 7 \in A_{d(v)}$, $d_{H_2}(v)\pmod 7 \in B_{d(v)}$
and $d(v)-d_{H_1}(v)-d_{H_2}(v)\pmod 7 \in C_{d(v)}$, where $A_{d(v)}\cup B_{d(v)}\cup C_{d(v)}$ constitutes a partition of $\mathbb{Z}_7$. For each edge $v_jv_i\in E$ with $j<i$ and $d(v_i)=d(v_j)=d$,
if $v_j\notin B'(v_i)$, then $v_i$ and $v_j$ are distinguishable by colour $1$, and in the remaining cases by colour $2$.
\end{proof}
%{\hfill $\Box$}

\section{Concluding Remarks}
Intriguingly, there is still lack of complete characterization of the family of graphs with well defined
`dal' parameter. Thus in general it is not known if a finite bound for the graph invariant in question
exists for these graphs, cf. Conjecture~\ref{upper_bound_con}.
Surprisingly vertices with `smaller' degree appear more difficult to handle with,
and seem to require a different approach.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}
\bibitem{Louigi2}
L.~Addario-Berry, R.~E.~L. Aldred, K.~Dalal, B.~A. Reed. \newblock  
Vertex colouring edge partitions. \newblock 
\emph{J. Combin. Theory Ser. B}, 94(2):237--244, 2005.

\bibitem{Louigi30}
L.~Addario-Berry, K.~Dalal, C.~McDiarmid, B.~A. Reed, A.~Thomason. \newblock
Vertex-Colouring Edge-Weightings. \newblock \emph{Combinatorica}, 27(1):1--12, 2007.

\bibitem{Louigi}
L.~Addario-Berry, K.~Dalal, B.~A. Reed. \newblock Degree Constrained Subgraphs. \newblock
\emph{Discrete Appl. Math.}, 156(7):1168--1174, 2008.

\bibitem{daltonisci}
R.~Kalinowski, M.~Pil\'sniak, J.~Przyby{\l}o, M.~Wo\'zniak. \newblock 
Can colour-blind distinguish colour pallets? \newblock 
\emph{Electron. J. Combin.}, 20(3):$\sharp$P23, 2013.

\bibitem{KalKarPf_123}
M.~Kalkowski M.~Karo\'nski, F.~Pfender. \newblock Vertex-coloring edge-weightings: Towards the 1-2-3 conjecture. \newblock \emph{J. Combin. Theory Ser. B}, 100:347--349, 2010.

\bibitem{123KLT}
M.~Karo\'nski, T.~\L uczak, A.~Thomason. \newblock Edge weights and
vertex colours. \newblock \emph{J. Combin. Theory Ser. B}, 91:151--157, 2004.

\bibitem{daltonisci1500}
J.~Przyby{\l}o. \newblock On colour-blind distinguishing colour pallets in regular
graphs. \newblock \emph{J. Comb. Optim.}, to appear.

\end{thebibliography}

\end{document}
