Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $G=(V,E)$ be a bipartite graph and e=uv an edge where $\text{deg}(u)<\Delta$. How can we create a graph G' by subdividing the edge e with a new degree two vertex z.

i.e: we delete $e$ and add a new vertex $z$ which is adjacent to $u$ and $v$.

Show that $X^E(G')=\Delta$.

$X^E(G')$ : the edge chromatic number of $G'$

share|cite|improve this question
The title doesn't really seem to match what the question apparently is (i.e. 'Show that $X^E(G') = \Delta$'). – Tara B Feb 12 '13 at 19:27

I assume it is known that for the bipartite graph $G$, $X^E(G)=\Delta$. Consider an according edge colouring. Let $\alpha$ be the colour of $uv$. Since $\operatorname{deg}(u)<\Delta$, there is at least one color $\beta$ not occuring for an edge incident with $u$. Assign $\alpha$ to $zv$ and $\beta$ to $uz$.

EDIT: It appears, we don't need that $G$ is bipartite. It is sufficient that $G$ is a class 1 graph and $\operatorname{deg}(u)<\Delta$.

share|cite|improve this answer
Good job supplying that implicit assumption. I was wondering whether we were supposed to bisect all edges rather than just one, but this interpretation makes more sense. – Henning Makholm Feb 12 '13 at 19:24
Technically, this only shows $X^E(G)\leq \Delta$. – Tara B Feb 12 '13 at 19:28
Yes, but it is know (and essentially trivially true that) $X^E(G)\geq \Delta$ for all graphs $G$, @TaraB. – Thomas Andrews Feb 12 '13 at 19:29
I was more or less being silly, but what is $\Delta$, actually? – Tara B Feb 12 '13 at 19:30
@TaraB I assume $\Delta=\max\{\operatorname{deg}(v)\mid v\in V\}$. – Hagen von Eitzen Feb 12 '13 at 19:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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