Document Type

Thesis

Degree Name

Master of Science (MSc)

Department

Physics and Computer Science

Program Name/Specialization

Applied Computing

Faculty/School

Faculty of Science

First Advisor

Kathie Cameron

Advisor Role

Professor

Second Advisor

Chinh Hoang

Advisor Role

Professor

Abstract

Given a set H of graphs, a graph G is H-free if it does not contain any graph in H as an induced subgraph. The complexity of the colouring problem is known when H is a set of graphs on four vertices, with three exceptions. One of those exceptions is the case of {claw, 4K1}-free graphs, for which our classes of {claw, 4K1, bridge}-free and {claw, 4K1, bridge,C4-twin}-free graphs are subclasses.

The original goal of this work was to prove that {claw, 4K1, bridge}-free graphs can be coloured in polynomial-time. We prove this for a subclass where the graph contains a cycle on seven vertices. We then look at a slightly larger set H that includes the graph called C4-twin. Using clique-width and theorems on perfect graphs, we show that {claw, 4K1, bridge, C4-twin}-free graphs are either perfect or have bounded clique-width and can thus be coloured in polynomial time.

Convocation Year

2023

Convocation Season

Fall

Download

Share

COinS