recategorized by
1,173 views
3 votes
3 votes

An undirected graph $G = (V, E)$ is said to be $k$-colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we have $c(u) \neq c(v)$. Which of the following statements is $\text{FALSE}$?

  1. $G$ is $\mid V \mid $ -colourable
  2. $G$ is $2$-colourable if there are no odd cycles in $G$
  3. $G$ is $(\Delta +1)$-colourable where $\Delta$ is the maximum degree in $G$
  4. There is a polynomial time algorithm to check if $G$ is $2$-colourable
  5. If $G$ has no triangle then it is $3$-colourable
recategorized by

4 Answers

0 votes
0 votes
1.True, for triangle it will be true

2. True. For even length cycle G is 2 colorable

3.True. For triangle , also for complete graph with 4 vertices it is possible

4.True

5. False. For triangle also it can be 3 colorable . Cycle of even length has no triangle, but it is 2 colorable.etc.
0 votes
0 votes
1 - definitely u can colour every vertex with unique colour.

2- If graph is 2 colourable then it is bipirated graph . and a graph is bipirated if and only if every cycle is of even length in it.

3- the condition is not give same colour to adjacent vertexes. so if it has a degree k then u need k+1 colour. one for itself and other need k. so try this u can easily say that this is the upper limit.

4- yes. check for bipirated graph. or every cycle is of even lenght or not. from point 2

5-if a graph has a cycle graph in itself . suppose it has cn ( cycle graph with 3 vertices. i.e a triangle ) then it requires atleast 3 colours, we can't say it always will
0 votes
0 votes
First of all, if a graph is k colourable, that means it is also k+i colourable for any positive i

Option A is true. Every graph of $v$ vertices is $v$ colourable. Just give each vertex it's own colour.


Option B is the definition of of bipartite graph.

Bipartite $\equiv$ 2 colourable $\equiv$ no-odd-length-cycle.

Option B is true

 

Option D asks if we have a polynomial time algorithm to check if a graph is bipartite. Yes, we have. (DFS)

Option D is true


Option C is true. Maximum degree gives us the maximum neighbours a node can have. Each neighbour gets a different colour.


Option E is false. The Grötzsch graph is a triangle-free graph that needs four colours.

Answer:

Related questions