**option A** is correct it should be 2

Dark Mode

9,770 views

43 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$

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

50 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$

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

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

5

0

12 votes

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.

1

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.

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