4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Just a quick question. Lemma two says that G has two adjacent edges of the same color. It doesn’t say it has the prescribed edges of the same color. The issue is that the edges are also prescribed, not just the vertex. Can you please clarify ... I have other comments and questions but perhaps this should be made precise first. We want two prescribed edges to be of the same color. Although I see how you might argue this, I prefer to make sure I understand what you have in mind with the symmetry of the complete graph. Apologies if I am slow or pedantic. $\endgroup$ – EGME May 10 at 20:02
  • $\begingroup$ I will ask my next question: can you make Lemma 2 work (in the complete graph, say) with three edges instead of two. We can worry about them being prescribed after this is established if possible. Thank you. $\endgroup$ – EGME May 10 at 20:18
  • 1
    $\begingroup$ @EGME You can prescribe the edge. No problem. 2-arc-transitivity means you can move a vertex and two of its incident edges wherever you want. The complete graph is 2-arc-transitive. Should I elaborate more on the symmetry? I have to think about the second question. I assume you want the three edges to be incident to a common vertex and to have the same color? Or is it enough that the three edges are pair-wise adjacent (eg. they form a triangle)? $\endgroup$ – M. Winter May 10 at 21:03
  • $\begingroup$ Apologies, I meant the three edges incident to a common vertex ... in the complete graph, it is easy to see that you can get a monochromatic triangle. $\endgroup$ – EGME May 10 at 21:43
  • $\begingroup$ I have edited the problem so as to have this question. $\endgroup$ – EGME May 11 at 8:35

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.