An edge coloring problem

Question

1) Suppose you have a simple graph $G$ with max degree $\Delta(G)=k-1$ and chromatic index $\chi’(G)=k$. Let $v\in V(G)$ be a vertex incident with edges $a, b\in E(G)$. Can you find an edge $k$-coloring which is proper except for having $a, b$ of the same color? And what if you assume the restriction that $|V(G)|=k$? If the answer is “yes”, how do you prove it? (M. Winter has provided a partial answer).

2) Suppose you have a simple graph $G$ with max degree $\Delta(G)=k-1$ and chromatic index $\chi’(G)=k$. Let $v\in V(G)$ be a vertex incident with edges $a, b, c\in E(G)$. Can you find an edge $k$-coloring which is proper except for having $a, b, c$ of the same color? And what if you assume the restriction that $|V(G)|=k$? Furthermore, what if $G=K_k$, the complete graph on $k$ vertices? If the answer is “yes”, how do you prove it?

There is a generalization of these questions which I would like to prove, but I guess this is a good starting point.

Answer 1

Tl;dr

There is always a vertex $v\in V(G)$ and and an edge-coloring that has two indentically colored edges incident to $v$, and is proper everywhere else.

If we want to prescribe the vertex $v$, then I can show that this at least still works when we have $|V(G)|=\chi'(G)=k$.

---

Let $G$ be a connected graph with $\chi'(G)=k$ and $\Delta(G)\le k-1$. Denote by $E(v)$ the set of edges incident to some $v\in V(G)$.

Let $G$ be properly colored with $k$ colors.

Lemma 1. There is an edge $e=vw\in E(G)$, so that the set of colors used in $E(v)$ is different from the set of colors used in $E(w)$.

Proof.

Assume that no such edge exists. Then any two adjacent vertices $v,w\in V(G)$ have the same set of colors in $E(v)$ and $E(w)$. Since $G$ is connected, every vertex uses the same colors on its incident edges. Since $\Delta(G)\le k-1$, this means the coloring uses actually at most $k-1$ colors. Contradiction.

$\square$

Lemma 2. There is a vertex $v\in V(G)$ and an edge-coloring of $G$ that has the same color on two edges incident to $v$, and is proper everywhere else.

Proof.

Choose an edge $e=vw\in E(G)$ with different sets of colors for $E(v)$ and $E(w)$ (which exists according to Lemma 1). Choose a color that is only used in one of the sets, say $E(v)$. Recolor $e$ with that color. Then $v$ has two edges of the same color, but the coloring is proper everywhere else.

$\square$

So there is one such a vertex. But can you choose the vertex arbitrarily? I cannot say this in general, but it works for the case $|V(G)|=k$.

Theorem. If $V(G)=k$ and $v\in V(G)$ a vertex, then there is an edge-coloring in which $v$ is incident to two edges of the same color and the edge-coloring is proper everywhere else.

Proof.

Consider $G$ as a subgraph of the complete graph $K_k$ by adding edges.

Obviously $\Delta(K_k)=k-1$, and it is known that

$$\chi'(K_k)=\begin{cases} k-1 &\text{if $k$ is even} \\ k & \text{if $k$ is odd}\end{cases}.$$

If $k$ would be even, then $\chi'(K_k)=k-1$, and this would restrict to a proper edge-coloring of $G$ with $k-1$ colors in contradiction to the assumption $\chi'(G)=k$. Hence $k$ is odd and $\chi'(K_k)=k$.

So the conditions for Lemma 2 are satisfied, and we can apply it to the complete graph $K_k$ and obtain a vertex $w$ and a coloring with the desired properties, especially it has the same color on $e,\bar e\in E(w)$.

Because of the symmetry of $K_k$ we can transform the coloring, so that $v=w$ and $e,\bar e\in G$ already. This gives the desired coloring for $G$.

$\square$

The symmetry argument works whenever you can consider $G$ as a spanning subgraph of a 2-arc-transitive graph $\bar G$ with $\Delta(\bar G)\le k-1$ and $\chi'(\bar G)=k$, like e.g. $\bar G=K_k$ in the case above. This then extends the theorem to $|V(G)|>k$.