Graph Theory — Problem Set: Graph Coloring & Isomorphism

GRAPH THEORY
Problem Set 3
Graph Coloring, Chromatic Numbers & Graph Isomorphism

Course Graph Theory

Topics Covered Coloring, Greedy Algorithm, Chromatic Number, Cliques, Isomorphism

Total Marks 50 marks

Instructions Label graphs clearly. A Viva out of this problem set will be conducted in the
upcoming lecture.

Question 1 — Map Coloring & Graph Representation

The following six cities are planning a regional conference. Each city has been assigned a time slot
for its presentation. Two cities conflict — and therefore cannot share the same conference room — if
their time slots overlap. The conflict graph is shown below, where each vertex represents a city and
each edge represents a scheduling conflict.

The vertices represent cities A through F with the following time slots:

City Time Slot City Time Slot

A 9:00 am – 10:30 am D 10:00 am – 11:31 am

B 9:00 am – 11:00 am E 10:20 am – 12:30 pm

C 10:31 am – 12:00 pm F 11:30 am – 1:00 pm

Graph Theory | Page 1

Graph Theory — Problem Set: Graph Coloring & Isomorphism

Figure 1: Conflict graph for city presentations (12 edges)

(a) Verify that the graph in Figure 1 correctly represents the conflict structure. List all pairs of
cities whose time slots overlap, and confirm each is reflected by an edge.
(b) Using a proper coloring of Figure 1, determine the minimum number of conference rooms
required. Each color represents a distinct room. State your coloring explicitly (e.g., "Room 1: {A,
E}, Room 2: {B, F}, ...").
(c) Explain in one or two sentences why this problem is equivalent to finding the chromatic
number of the conflict graph.
[12 marks]

Question 2 — Chromatic Number: Upper and Lower Bounds

Consider the graph below, which consists of a 5-cycle with a central "hub" vertex v6 connected to
all five outer vertices.

Graph Theory | Page 2

Graph Theory — Problem Set: Graph Coloring & Isomorphism

(a) Determine the degree of each vertex. What is the maximum degree Δ(G)? Use this to state
an upper bound on the chromatic number χ(G).
(b) Identify the largest clique in this graph. Use it to state a lower bound on χ(G).
(c) Determine χ(G) exactly and provide a valid coloring that achieves it. Draw or describe your
coloring clearly.
(d) A graph G is said to be k-chromatic if χ(G) = k. What is k for this graph.
[13 marks]

Question 3 — The Greedy Coloring Algorithm

Consider the graph G shown below.

Figure 3: Graph G for greedy coloring analysis

The edge set of G is: { ab, ac, ad, bc, bd, cd, ce, de }. Apply the Greedy Coloring Algorithm using the
available colors: Color 1 (Red), Color 2 (Blue), Color 3 (Green), Color 4 (Yellow), assigning the lowest-
numbered valid color at each step.

(a) Apply the greedy algorithm using the vertex ordering: a, b, c, d, e. Record the color assigned
at each step. How many colors does this ordering require?
(b) Is there an ordering that achieves the chromatic number χ(G) for this graph? If so, provide it.
If not, explain why.
[10 marks]

Graph Theory | Page 3

Graph Theory — Problem Set: Graph Coloring & Isomorphism

Graph Isomorphism
Background: What is Graph Isomorphism?

In mathematics, two objects are isomorphic if they have the same structure — they are, in a precise
sense, "the same thing in disguise." In graph theory, two graphs can look visually very different
(different layouts, different vertex labels, different arrangements) and yet have identical structure.

Formally, two graphs G = (V, E) and H = (V', E') are said to be isomorphic, written G ≅ H, if there
exists a bijection (a one-to-one and onto function):

f : V(G) → V(H)
such that for any two vertices u, v ∈ V(G):

{u, v} ∈ E(G) ⟺ {f(u), f(v)} ∈ E(H)

In plain language: two vertices are adjacent in G if and only if their images under f are adjacent in H.
The function f is called an isomorphism. It is essentially a relabeling of vertices that perfectly
preserves all edges.

Key Necessary Conditions for Isomorphism (but not sufficient on their own)
• Both graphs must have the same number of vertices |V(G)| = |V(H)|.
• Both graphs must have the same number of edges |E(G)| = |E(H)|.
• Both graphs must have the same degree sequence.
• Both graphs must have the same number of connected components.
• Both graphs must have the same chromatic number χ(G) = χ(H).
• Both graphs must have the same clique number ω(G) = ω(H).

Satisfying all of the above does NOT guarantee isomorphism — it only rules out non-
isomorphism.

Question 4 — Graph Isomorphism

Consider the two graphs G and H shown below. They have the same number of vertices and
edges, and at first glance it is not obvious whether they are isomorphic.

Graph Theory | Page 4

Graph Theory — Problem Set: Graph Coloring & Isomorphism

Figure 6: Graphs G (vertices 1–5) and H (vertices a–e) — are they isomorphic?

Graph G has vertex set {1, 2, 3, 4, 5} with edges: { 12, 13, 14, 15, 23, 24, 35 }.
Graph H has vertex set {a, b, c, d, e} with edges: { ab, ac, ad, ae, bc, bd, ce }.

(a) Check all three necessary conditions: verify that G and H have the same number of
vertices, edges, and the same degree sequence. Present the degree sequence of each graph in
non-decreasing order.
(b) Based on your analysis in (a), can you already determine whether G and H are isomorphic
or not? Explain your reasoning.
(c) Attempt to construct an explicit isomorphism f : V(G) → V(H) — that is, define f(1), f(2), f(3),
f(4), f(5) and verify that every edge in G maps to an edge in H and vice versa. If you succeed,
write out the full verification table. If you believe no isomorphism exists, prove it.
[15 marks]

Graph Theory | Page 5