search
Log In
34 votes
4.6k views

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$
in Graph Theory
edited by
4.6k views
–4
n-1
0
what about the wheel graph?
0
What is minimum number for EDGE coloring? (I'm getting 3 as I find Edge-coloing instead of vertex during test, so dumb!)
3

option A is correct it should be 2

0

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. 

1

@Shashank shekhar D 1

A wheel graph will have n cycles of length 3, which is odd and not allowed.

9 Answers

42 votes
 
Best answer

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

Correct Answer: $A$


edited by
5

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
Yes in this case you are geting (n-1) as a chromatic number, but this is subset.
31
No, in this case you always getting 2 as a chromatic number . The middle node of  graph is 1 and its surroundings are 2 ,2, 2... same color.
8
Star graphs always have chromatic no 2
1

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.

0
In start graph we can color it in more then 2 and more then 2 colors but chromatic number means minimum of vertex coloring so for star graph it is 2.
0
Sir, refrerence link that you provided are not working. Can you please store these pdf files on google drive and share link with us.
12 votes
2 draw some random graph and you will realise that 2 is the chromatic number
0
as every complete graph is simple

using k4 no chromatic = n

im wrong?
0

@ Registered user 11 in K4 we have cycles of length 3 which is odd.

0
yes we can assume 2 regular graph for no odd length cycle graph
0

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

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.

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..
0

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 ?

1

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?

2
Wheel graph contains odd length cycle.
0
ohh, two outer vertices connecting with inner (central) vertex forms odd length cycle.
A big miss. :P
Thanks.
0
Question is about not having odd length cycle. You have a cycle of 3 here
5 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.
0 votes
2 bcoz bipirtite graph
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.
0 votes

given graph is bipartite
every bipartite is 2 colorable
hence 2 is answer

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.
Answer:

Related questions

33 votes
4 answers
1
3.5k views
Which one of the following is TRUE for any simple connected undirected graph with more than $2$ vertices? No two vertices have the same degree. At least two vertices have the same degree. At least three vertices have the same degree. All vertices have the same degree.
asked Sep 15, 2014 in Graph Theory gatecse 3.5k views
27 votes
5 answers
2
6.6k views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
asked Feb 12, 2016 in Graph Theory Akash Kanase 6.6k views
41 votes
5 answers
3
4.2k views
Consider the undirected graph $G$ defined as follows. The vertices of $G$ are bit strings of length $n$. We have an edge between vertex $u$ and vertex $v$ if and only if $u$ and $v$ differ in exactly one bit position (in other words, $v$ can be obtained from $u$ by flipping a single bit). ... $\left(\frac{1}{n}\right)$ $\left(\frac{2}{n}\right)$ $\left(\frac{3}{n}\right)$
asked Oct 31, 2014 in Graph Theory Ishrat Jahan 4.2k views
25 votes
3 answers
4
2.7k views
What is the chromatic number of the following graph? $2$ $3$ $4$ $5$
asked Oct 28, 2014 in Graph Theory Ishrat Jahan 2.7k views
...