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.0k 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.
0 votes 0 votes it's even-length cycle graph i.e C2, C4,C6......all need max 2 colour so chromatic number X(G)=2 Prateek kumar answered Jan 29, 2017 Prateek kumar comment Share Follow See all 2 Comments See all 2 2 Comments reply Puja Mishra commented Jan 2, 2018 reply Follow Share No its nt ... Question has said that simple connected graph which does not contain any odd length cycle ...It does nt imply that it has even length cycle ... 1 votes 1 votes Lakshman Bhaiya commented Jan 29, 2018 reply Follow Share The question says that does not contain odd- length cycle, it means that it contains even-length cycle or may not contains the even-length cycle, or contain both of them.(But not Odd length cycle). 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Answer : 2 Intuition : If we observe the question, tree is one of the example which satisfies the requirements of given question. Now , irrespective of number of nodes, chromatic number of any tree is 2. HeadShot answered Jan 3, 2019 HeadShot comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes given graph is bipartite every bipartite is 2 colorable hence 2 is answer Rajesh Panwar answered Jan 6, 2019 Rajesh Panwar comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes As the Question says that G must not have a odd length cycle then we can simply take any G which has even length cycle say $C_2{}$ , $C_4{}$ ,etc.and solve to get chromatic no as 2. Chirag Shilwant answered Jul 19, 2020 Chirag Shilwant comment Share Follow See all 0 reply Please log in or register to add a comment.