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$. $2$ $3$ $n-1$ $n$ Graph Theory gatecse-2009 graph-theory graph-coloring normal + – gatecse asked Sep 15, 2014 • edited May 25, 2018 by kenzou gatecse 13.5k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Rishav Kumar Singh commented Aug 17, 2018 reply Follow Share option A is correct it should be 2 5 votes 5 votes ankitgupta.1729 commented Sep 6, 2018 reply Follow Share What is minimum number for EDGE coloring It depends on the maximum degree of the given graph. If maximum degree of the simple undirected graph is $d_{max}$ , It means we need atleast $d_{max}$ colors necessarily to proper color the whole graph but it is not sufficient.We may need $d_{max} + 1$ colors also for proper edge coloring of the graph but no more than $d_{max} + 1$ colors are required. Edge chromatic number or chromatic index of any simple undirected graph is either $d_{max}$ or $d_{max} + 1$ according to Vizing's Theorem. 3 votes 3 votes Abhishar Sinha commented Jan 23, 2019 reply Follow Share @Shashank shekhar D 1 A wheel graph will have n cycles of length 3, which is odd and not allowed. 2 votes 2 votes Please log in or register to add a comment.
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$ Mithlesh Upadhyay answered Jun 4, 2015 • edited Apr 23, 2019 by Naveen Kumar 3 Mithlesh Upadhyay comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Deepak Poonia commented May 14, 2021 reply Follow Share In short, Since Graph ($G$) does not contain any odd length cycle, So, $G$ is bipartite. Chromatic number of Bipartite graph is at most $2.$ Since $G$ has at least two vertices and also $G$ is connected, So, $G$ has at least one edge, hence, $G$ cannot be colored with one color. So, answer will be $2.$ 9 votes 9 votes Pranavpurkar commented Apr 17, 2022 reply Follow Share Deepak PooniaSir I think atleast 3 vertices not 2 ! but with 3 vertices the only constraint here is that we cannot have 3 edges bcoz it will form odd length cycle . 0 votes 0 votes Deepak Poonia commented Jul 18, 2022 reply Follow Share @Pranavpurkar For a Connected graph with at least 2 vertices, Chromatic Number is At Least 2. My previous statement is correct. 0 votes 0 votes Please log in or register to add a comment.
11 votes 11 votes 2 draw some random graph and you will realise that 2 is the chromatic number Bhagirathi answered Nov 25, 2014 Bhagirathi comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Registered user 31 commented Nov 15, 2016 reply Follow Share 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 ? 0 votes 0 votes Warrior commented Oct 23, 2017 reply Follow Share @ 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. 1 votes 1 votes JAINchiNMay commented Nov 4, 2022 reply Follow Share This is not an answer :( 0 votes 0 votes Please log in or register to add a comment.
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.. sonu answered Nov 25, 2014 sonu comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Sanket Kumar Mali commented Jan 2, 2017 reply Follow Share Wheel graph contains odd length cycle. 3 votes 3 votes Shashank shekhar D 1 commented Jan 2, 2017 reply Follow Share ohh, two outer vertices connecting with inner (central) vertex forms odd length cycle. A big miss. :P Thanks. 0 votes 0 votes Shatadru RC commented Oct 21, 2017 reply Follow Share Question is about not having odd length cycle. You have a cycle of 3 here 0 votes 0 votes Please log in or register to add a comment.
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. Chhotu answered Sep 19, 2017 Chhotu comment Share Follow See all 0 reply Please log in or register to add a comment.