Dark Mode

606 views

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}$?

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

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

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

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

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

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.