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 |
| _version_ | 1848766358294102016 |
|---|---|
| author | Alex, James |
| author_facet | Alex, James |
| author_sort | Alex, James |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T11:49:52Z |
| format | Thesis |
| id | curtin-20.500.11937-98074 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T11:49:52Z |
| publishDate | 2025 |
| publisher | Curtin University |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-980742025-07-11T06:14:30Z Perfect Graphs and its Extensions Alex, James 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. 2025 Thesis http://hdl.handle.net/20.500.11937/98074 Curtin University restricted |
| spellingShingle | Alex, James Perfect Graphs and its Extensions |
| title | Perfect Graphs and its Extensions |
| title_full | Perfect Graphs and its Extensions |
| title_fullStr | Perfect Graphs and its Extensions |
| title_full_unstemmed | Perfect Graphs and its Extensions |
| title_short | Perfect Graphs and its Extensions |
| title_sort | perfect graphs and its extensions |
| url | http://hdl.handle.net/20.500.11937/98074 |