Virtual Labs

Tools

Aim

Theory

Pretest

Procedure

Simulation

Posttest

References

Feedback

Aim

Theory

Pretest

Procedure

Simulation

Posttest

References

Feedback

Graph Colouring

Choose difficulty:

Beginner

Intermediate

Advanced

Which of the following is not a type of graph in computer science?

a: undirected graph Explanation

Explanation

b: bar graph Explanation

Explanation

c: directed graph Explanation

Explanation

d: weighted graph Explanation

Explanation

What is vertex coloring of a graph?

a: A condition where any two vertices having a common edge should not have same color Explanation

Explanation

b: A condition where any two vertices having a common edge should always have same color Explanation

Explanation

c: A condition where all vertices should have a different color Explanation

Explanation

d: A condition where all vertices should have same color Explanation

Explanation

In a properly vertex-coloured graph, what can you say about the colours of connected vertices (vertices with an edge between them)?

a: They must all have the same colour Explanation

Explanation

b: They must all have different colours Explanation

Explanation

c: They can have any colour Explanation

Explanation

d: None of the above Explanation

Explanation

A graph G has a chromatic number of 2. What can you conclude about G?

a: G is a complete graph. Explanation

Explanation

b: G is a bipartite graph. Explanation

Explanation

c: G can only be coloured with exactly 2 colours. Explanation

Explanation

d: G must have an even number of vertices. Explanation

Explanation

A friend claims they coloured a graph with 10 vertices and only needed 1 colour. Is this possible?

a: No, this is not possible for any graph with more than 1 vertex Explanation

Explanation

b: Yes, it's always possible to colour any graph with just 1 colour Explanation

Explanation

c: It depends on the specific connections in the graph Explanation

Explanation

d: Maybe, but it's very unlikely. Explanation

Explanation

Community Links Sakshat Portal Outreach Portal FAQ: Virtual Labs

AGPL 3.0 & Creative Commons (CC BY-NC-SA 4.0)