Take the 2-minute tour ×
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.

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|improve this question
1  
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
add comment

1 Answer

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|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
1  
Technically, this only shows $X^E(G)\leq \Delta$. –  Tara B Feb 12 '13 at 19:28
1  
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
1  
@TaraB I assume $\Delta=\max\{\operatorname{deg}(v)\mid v\in V\}$. –  Hagen von Eitzen Feb 12 '13 at 19:31
show 2 more comments

Your Answer

 
discard

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.