# “Good” edge-colorings

Let $n >1$ be an integer, and suppose $G = (V,E)$ is a simple undirected graph with $V = \{1,\ldots,n\}$. For $v\in V$ set $N(v) = \{w\in V: \{v,w\} \in E\}$.

It is known by Vizing's theorem that the edges of $G$ can be colored with $\Delta(G)+1$ colors (where $\Delta(\cdot)$ denotes the maximum degree), and of course we have $\Delta(G)+1 \leq n$.

\We call an edge-coloring $c:E\to \{1,\ldots,n\}$ good if for all $x\neq y\in V$ with $\{x,y\} \in E$ we have $c(\{x,y\}) \in N(x)\cup N(y).$

Does every simple undirected graph $G=(\{1,\ldots,n\},E)$ have a good edge-coloring?

• I assume you actually want $V=\{1,\dots, n\}$ and not just $|V|=n$? – Tony Huynh Feb 12 '17 at 16:07
• It immediately follows from the edge choosability conjecture, but maybe is weak enough to be provable. – Fedor Petrov Feb 12 '17 at 16:26
• @FedorPetrov : How does it follow? The lists here have different sizes. – Timothy Chow Feb 13 '17 at 3:55
• @TimothyChow Oh - can't you prove your assertion by noting that the edge coloring number is always $\Delta$ or $\Delta+1$? -> en.wikipedia.org/wiki/Vizing%27s_theorem . I wrote this in a hurry, and I might be completely wrong – Dominic van der Zypen Feb 13 '17 at 16:40
• @DominicvanderZypen : Ah, yes, of course. So maybe one should look at algorithms for Vizing's theorem to see if any of them can be adapted for this problem. – Timothy Chow Feb 13 '17 at 17:07

Basically, the nodes are colored with the colors 1 to n here, and the edges should be colored with the same colors. In addition to that, the set of colors that are allowed for an edge $$\{u,v\}$$ is restricted to $$N(u) \cup N(v)$$, i.e. to the colors that are locally available in the neighborhood of $$u$$ and $$v$$.
We could call an edge coloring strongly local, if the palette for edge $$\{u,v\}$$ is restricted to $$u$$ and $$v$$ themselves, and local, if it is only restricted to $$N(u) \cup N(v)$$.
• Any circular graph $$C_n$$ has a strongly local edge coloring.
• The complete graph $$K_4$$ does not have a strongly local edge coloring.
• Any $$K_n$$ has a local edge coloring, because $$N(u) \cup N(v) = V$$, so the locality condition does not impose a real restriction in complete graphs.