"Good" edge-colorings

Question

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?

Answer 1

I don't have a solution yet, but I propose to call this a local edge coloring instead of a good one.

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)$.

Examples:

• 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.