# “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 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.