What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$.
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$ [email protected] 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) [email protected] 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 ) [email protected] http://math.ucsb.edu/~padraic/mathcamp_2011/introGT/MC2011_intro_to_GT_wk1_day4.pdf
What if I have a graph like below ? These would be simple graphs without any odd length, right ? So should we not have (n - 1) as the answer ?
@ Registered user 31 for given above graphs chromatic no is 2 not (n-1), one colour for middle node and another colour for all the remaining nodes.
Great [email protected]Mithlesh Upadhyay
@ Registered user 11 in K4 we have cycles of length 3 which is odd.
well, for these graphs, chromatic no. will be 2 only, because all the degree one vertices are not adjacent to any other vertex, so they can take the same color, and center can take another.
But I have a concern with wheel graph like the one below. Its chromatic no. will be 3. then why is the ans 2?
Gatecse