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

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

Improve this question
$\endgroup$
10
  • $\begingroup$ I assume you actually want $V=\{1,\dots, n\}$ and not just $|V|=n$? $\endgroup$
    – Tony Huynh
    Commented 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$
    – Fedor Petrov
    Commented Feb 12, 2017 at 16:26
  • 1
    $\begingroup$ @FedorPetrov : How does it follow? The lists here have different sizes. $\endgroup$
    – Timothy Chow
    Commented 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$
    – Dominic van der Zypen
    Commented 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$
    – Timothy Chow
    Commented Feb 13, 2017 at 17:07

1 Answer 1

Reset to default
3
$\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.
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .