## Theses and Dissertations (Comprehensive)

#### Title

Vertex coloring with forbidden subgraphs

Thesis

#### Degree Name

Master of Applied Computing

#### Department

Physics and Computer Science

#### Program Name/Specialization

Applied Computing

#### Faculty/School

Faculty of Science

Chinh Hoang

Professor

Angele Hamel

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.

2019

Spring

COinS