Document Type

Thesis

Degree Name

Master of Applied Computing

Department

Physics and Computer Science

Program Name/Specialization

Applied Computing

Faculty/School

Faculty of Science

First Advisor

Chinh Hoang

Advisor Role

Professor

Second Advisor

Angele Hamel

Advisor Role

Professor

Abstract

Given a set $L$ of graphs, a graph $G$ is $L$-free if $G$ does not contain any graph in $L$ as induced subgraph. A $hole$ is an induced cycle of length at least $4$. A $hole$-$twin$ is a graph obtained by adding a vertex adjacent to three consecutive vertices in a $hole$. Hole-twins are closely related to the characterization of the line graphs in terms of forbidden subgraphs.

By using {\it clique-width} and {\it perfect graphs} theory, we show that ($claw$,$4K_1$,$hole$-$twin$)-free graphs and ($4K_1$,$hole$-$twin$,$5$-$wheel$)-free graphs are either perfect or have bounded clique-width. And thus the coloring of them can be done in polynomial time.

Convocation Year

2019

Convocation Season

Spring

Download

Share

COinS