edited by
13,009 views
49 votes
49 votes

What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n  > 2$.

  1. $2$
  2. $3$
  3. $n-1$   
  4. $n$
edited by

11 Answers

Best answer
57 votes
57 votes

Lemma $1:$ $G$ is bipartite, if and only if it does not contain any cycle of odd length.

Proof. Suppose $G$ has an odd cycle. Then obviously it cannot be bipartite, because no odd cycle is $2$-colorable. Conversely, suppose $G$ has no odd cycle. Then we can color the vertices greedily by $2$ colors, always choosing a different color for a neighbor of some vertex which has been colored already. Any additional edges are consistent with our coloring, otherwise they would close a cycle of odd length with the edges we considered already. The easiest extremal question is about the maximum possible number of edges in a bipartite graph on $n$ vertices. $1$ ref@ http://math.mit.edu/~fox/MAT307-lecture07.pdf

Bipartite Graph: A graph which is $2$-colorable is called bipartite. We have already seen several bipartite graphs, including paths, cycles with even length, and the graph of the cube (but not any other regular polyhedra)

ref@ http://ocw.mit.edu/high-school/mathematics/combinatorics-the-fine-art-of-counting/lecture-notes/MITHFH_lecturenotes_9.pdf
$3.$ Bipartite graphs: By definition, every bipartite graph with at least one edge has chromatic number $2.$ (otherwise $1$ if graph is null graph )

ref@ http://math.ucsb.edu/~padraic/mathcamp_2011/introGT/MC2011_intro_to_GT_wk1_day4.pdf

Correct Answer: $A$

edited by
11 votes
11 votes
2 draw some random graph and you will realise that 2 is the chromatic number
8 votes
8 votes
No odd length cycle means no 3,5,7,... Length cycle should be there. So it means we can color this with less than 3 colors. Becz a presence of 3 length cycle will atlst need 3 colors to be colored. So here 2 color will work..
6 votes
6 votes
Consider this Graph as composition of even length(0, 2, 4 etc) cycles. And each even length cycle could be colored using two colors without creating any conflict. Process is as following -->

(1) Choose any vertices give color X.

(2) Give color Y to its neighbors.

Now this Y can not create conflict with X otherwise ood length cycle will appear. We can repeat this alternate coloring process until all vertices are not colored.

Means all the vertices which are odd no of  edges  away from First vertex will get Y color and remaining will get X color. During this process at any point  if problem comes it means an odd length cycle is present in our graph which is failing our assumption.
Answer:

Related questions

54 votes
54 votes
7 answers
1
43 votes
43 votes
4 answers
2
Akash Kanase asked Feb 12, 2016
15,315 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
46 votes
46 votes
6 answers
3
Kathleen asked Sep 15, 2014
11,046 views
The minimum number of colours required to colour the vertices of a cycle with $n$ nodes in such a way that no two adjacent nodes have the same colour is$2$$3$$4$$n-2 \lef...