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?

  • $\begingroup$ I assume you actually want $V=\{1,\dots, n\}$ and not just $|V|=n$? $\endgroup$
    – Tony Huynh
    Feb 12, 2017 at 16:07
  • 1
    $\begingroup$ It immediately follows from the edge choosability conjecture, but maybe is weak enough to be provable. $\endgroup$ Feb 12, 2017 at 16:26
  • 1
    $\begingroup$ @FedorPetrov : How does it follow? The lists here have different sizes. $\endgroup$ Feb 13, 2017 at 3:55
  • 3
    $\begingroup$ @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 $\endgroup$ Feb 13, 2017 at 16:40
  • 2
    $\begingroup$ @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. $\endgroup$ Feb 13, 2017 at 17:07

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


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.