Perfect Graphs and its Extensions

Alex, James

Access Status

Fulltext not available

Embargo Lift Date

2027-06-30

Authors

Alex, James

Date

2025

Supervisor

Guanglu Zhou

Louis Caccetta

Type

Thesis

Award

PhD

Metadata

Show full item record

Faculty

Science and Engineering

School

School of Electrical Engineering, Computing and Mathematical Sciences

URI

http://hdl.handle.net/20.500.11937/98074

Collection

Curtin Theses

Abstract

This thesis investigates perfect graphs and its extensions, focusing on induced and non-induced star-perfect graphs, as well as strongly-perfect graphs. It presents an alternative proof to Lovász's characterization (1972) and characterizes induced star-perfect graphs in terms of minimal forbidden induced subgraphs. The thesis also identifies classes of non-induced star-perfect graphs and formulates its invariants using integer-programming. Additionally, a new list of sp-critical graphs and a sufficient condition for a graph to be strongly-perfect is presented.