2
$\begingroup$

Prove that if $G$ is a graph in which every edge is a part of at most one odd length cycle, then the graph is 3 colorable.

I want to show that if a graph is 4-critical there are two odd cycles which share an edge, which would prove the question. I'm not sure how to get that. I thought to take a maximum path, and then an end point has at least 3 neighbours in the path, which ensures 3 cycles, but I don't see a reason they can't all be even.

$\endgroup$
3
$\begingroup$

Here are some hints that lead to a proof.

Show that a 2-connected graph in which every edge is on at most one odd cycle is either bipartite or an odd cycle (e.g. by using an ear decomposition).

Show that the chromatic number of a graph equals the maximum of the chromatic numbers of its blocks.

As an alternative for the second part: use induction on the number of vertices. If $G$ is 2-connected we proved it in the first part. Otherwise $G$ has a cut vertex $v$. For a component $C$ of $G-v$ show that the conditions of the problem hold in $C+v$ (since cycles must be contained completely in one such enhanced component). So you can use the induction hypothesis on each such component ($+v$) and glue them together (you can always make sure that $v$ has color 1 in each of them).

$\endgroup$
  • $\begingroup$ I'm not familiar with the concepts of block or ear decomposition. Could you attempt to expand the proof please? $\endgroup$ – ctlaltdefeat Feb 12 '15 at 11:09
  • $\begingroup$ I had the impression that connectivity was normally treated before coloring. Anyway, see en.wikipedia.org/wiki/Ear_decomposition for an explanation of ear decomposition. A block is a 2-connected component. But if you are unfamiliar with these concepts you are probably not intended to come up with this proof. Maybe there is a simpler one. $\endgroup$ – Leen Droogendijk Feb 12 '15 at 11:28
  • $\begingroup$ We did study connectivity (I know for example that in a 2 connected graph there are at least two disjoint paths between every pair of vertices), we just didn't learn (I think :p) about ear decomposition or blocks. In any case I can prove the first hint and it looks like the second requires some work. Overall thanks as the solution works although indeed I think this isn't what was expected. $\endgroup$ – ctlaltdefeat Feb 12 '15 at 12:30
  • 1
    $\begingroup$ I added an alternative for the second part that may be closer to your current knowledge. $\endgroup$ – Leen Droogendijk Feb 12 '15 at 13:32
2
$\begingroup$

You can use induction on the number of odd cycles in G.

Assume that number is 0. Then G is bipartite and so 3-colorable. For the induction step, assume G has k+1 odd cycles. Remove an edge $e=(u,v)$ that belongs to one of the odd cycles. So, $G-e$ contains $k$ odd cycles with every edge belonging to at most one of them, and so can be 3-colored. Let $f$ be such a coloring of $G$.

Now, we try to add $e$ to $G$. If $f(u)\neq f(v)$ then $e$ can be safely added back to $G$. Else, assume w.l.o.g that $f(v)=f(u)=1$, and define $G_{ij}$, for $i<j\in {1,2,3}$ to be the sub-graph of $G$ containing only vertices whose color in $f$ is $i$ or $j$. Note that in every connected component of $G_{ij}$ it is possible to switch the color of every vertex while still having a legal coloring. So, if $u,v$ belong to different connected components of $G_{12}$ or $G_{13}$ the color of one of them can be changed, allowing $e$ to be added safely back to the graph.

If this is not the case, than $u,v$ belong to the same connected component in both $G_{12}, G_{13}$. So, there is a path $p_1:u\rightsquigarrow v$ in $G_{12}$ with all vertices colored 1 or 2. Note that since $u,v$ are colored 1, the path must be of even length. In the same manner, there is an even length path $p_2:u\rightsquigarrow v$ with all vertices colored only in 1 and 3. Clearly, $p_1,p_2$ are edge-disjoint. For each of these paths, the edge $e=(u,v)$ closes an odd-length cycle, and so $e$ belongs to two odd-length cycle, in contradiction to the assumption that it belongs to at most one.

$\endgroup$
1
$\begingroup$

As so often in graph theory, we can attempt a proof by looking for a minimal counter-example.

Let $G(V,E)$ be a graph where every edge is part of at most one odd cycle. Let $\mathcal C$ be the set of all valid colurings $c\colon V\to\{1,\ldots,\chi(G)\}$. Let $m=\min\{\,|c^{-1}(1)|:c\in\mathcal C\,\}$ and $\mathcal C_1=\{\,c\in\mathcal C:|c^{-1}(1)|=m\,\}$. Pick $c_1\in\mathcal C_1$ and $v_1\in c_1^{-1}(1)$ (which is possible because $m>0$ by definition of $\chi$). For $c\in\mathcal C_1$ let $f(c)=|\{\,u\in c^{-1}(2):v_1u\in E\,\}|$. Let $n=\min\{\,f(c):c\in \mathcal C_1\,\}$. Let $\mathcal C_2=\{\,c\in\mathcal C_1:f(c)=n\,\}$ and pick $c_2\in\mathcal C_2$. Then $n>0$ because otherwise $\tilde c\colon v\mapsto\begin{cases}2&\text{if $v=v_1$}\\c_2(v)&\text{otherwise}\end{cases}$ would be a colouring with $|\tilde c^{-1}(1)|<m$. Thus we can pick $v_2$ with $v_1v_2\in E $ and $c_2(v_2)=2$. Let $v_3$ be a neighbour of $v_1$ with $c_2(v_3)\ne 2$ and assume there is a path from $v_2$ to $v_3$ using only vertices of colours $2$ and $c_2(v_3)$. Then this path together with $v_3v_1$ and $v_1v_2$ is an odd cycle containg $v_1v_2$. By assumption, there can be at most one such neighbour $v_3$. Let $a=c(v_3)$ if such $v_3$ exists, otherwise let $a=3$. Assume there exists $b\in\{1,\ldots,\chi(G)\}\setminus\{1,2,a\}$. Consider the subgraph $(V,\{uw\in E: \{c_2(u),c_2(w)\}=\{2,b\}\})$ of $G$ amd let $H$ be the connected component of $v_2$ in it. Then $$ \hat c(v)=\begin{cases}b+2-c_2(v)&\text{if $v\in H$}\\c_2(v)&\text{otherwise}\end{cases}$$ is a valid colouring, is $\in\mathcal C_1$ and has $f(\hat c)<n$, contradiction. Therefore the assumpotion that $b$ as above exists mus be wrong. We conclude that $\chi(G)\le 3$.

$\endgroup$

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.