Virtual Labs

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

What is the minimum number of colors needed to properly color a cycle graph with 5 vertices (C5)?

a: 2 colors Explanation

Explanation

b: 3 colors Explanation

Explanation

c: 4 colors Explanation

Explanation

d: 5 colors Explanation

Explanation

What is the chromatic number of a complete graph with n vertices (Kn)?

a: 1 Explanation

Explanation

b: 2 Explanation

Explanation

c: n/2 Explanation

Explanation

d: n Explanation

Explanation

In graph coloring, what is Brooks' theorem?

a: Every graph can be colored with maximum degree + 1 colors Explanation

Explanation

b: For any connected graph G that is not complete or an odd cycle, χ(G) ≤ Δ(G) Explanation

Explanation

c: All planar graphs can be colored with 4 colors Explanation

Explanation

d: The chromatic number is always equal to the maximum degree Explanation

Explanation

What is the Mycielski construction and what does it prove about graph coloring?

a: It creates planar graphs with chromatic number 4 Explanation

Explanation

b: It generates graphs with high chromatic number and low clique number Explanation

Explanation

c: It proves that all graphs are 3-colorable Explanation

Explanation

d: It shows that all graphs need at least n colors Explanation

Explanation

Graph Colouring