I have this problem that is giving me fits. This problem seems similar to proving that the max coloring of vertices, where the max vertex degree is D, is D + 1.
We cannot have two edges that share the same endpoint be the same color.
My intuition is that we have to use induction on the number of edges. However, I'm not sure how to piece it together with the endpoint vertex involved.
Does anyone know how to approach this type of problem?
Best Answer
I think the statement is $\chi'(G) \leq 2\triangle(G)-1$. This can be done using induction on the number of edges of a graph. So
Base case: Let $G$ be a graph such that $|E(G)|=1$, then $\triangle(G) =1$,where $\triangle(G)$ is the maximum degree of $G$. so then $\chi'(G)=1\leq2*\triangle(G)-1$.
Inductive step: Suppose the claim is true for all graph such that $|E(G)|=n$, then now consider a graph $G$ such that $|E(G)|=n+1$. Pick an arbitrary edge $uv=e\in E(G)$, and consider $G'=G-e$. $\chi'(G')\leq 2\triangle(G')-1 \leq 2\triangle(G)-1$ by induction hypothesis. Now $deg(u) \leq \triangle(G)-1$ and $deg(v) \leq \triangle(G)-1$. So we can color $e$ using one more color different than all color on the edges incident to $u$ and $v$. So we can use one of $2\triangle(G)-1$ color to color $e$. so $\chi(G) \leq 2\triangle(G)-1$. I hope this is correct.