Perfect Graphs and its Extensions
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 forbidd...
| Main Author: | |
|---|---|
| Format: | Thesis |
| Published: |
Curtin University
2025
|
| Online Access: | http://hdl.handle.net/20.500.11937/98074 |
| Summary: | 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. |
|---|