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 If n≥ 2 and there are no odd length cycles, Then it is bipartite graph. A bipartite graph has the chromatic number 2. Eg: Consider a square, which has 4 edges. It can be represented as bipartite ,with chromatic number 2. keshore muralidharan answered Aug 28, 2020 keshore muralidharan comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes option A is correct rish1602 answered May 7, 2021 edited Jun 1, 2021 by rish1602 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes short trick akshay_123 answered Oct 8, 2023 akshay_123 comment Share Follow See all 0 reply Please log in or register to add a comment.