12
$\begingroup$

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?

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

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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