in Others edited by
474 views
2 votes
2 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
in Others edited by
474 views

4 Answers

1 vote
1 vote
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.

2 Comments

for point number 5..."for triangle also it can be 3 colorable". contradiction point - K4(complete graph with 4 vertices) has triangle and is not 3-colorable,,we need 4 color to color K4. here question is saying that graph contains triangle. why i am saying that the 5th point is true that any graph who doesn't contain triangle can be coloured with 3 colors (that's what 3 colorable means here). best example is C5(cycle graph with 5 vertices)
1
1

yes.But I think it is also supporting my answer

Say, G has triangle=p

 it is 3-colorable=q

then statement says ~p→q =pvq

negation of it says ~(p+q)=~p ∧ ~q

i.e. there is no triangle and it is not 3 colorable.

But Cycle of  length 5 (which has no triangle) is 3 colorable 

          

1
1
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