| EPSRC Reference: |
GR/R35629/01 |
| Title: |
Graph Decompositions and Perfect Graphs |
| Principal Investigator: |
Vuskovic, Professor K |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Fast Stream |
| Starts: |
01 June 2001 |
Ends: |
28 February 2005 |
Value (£): |
29,730
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
One of the main open problems in graph theory is the Strong Perfect Graph Conjecture (SPGC), which states that a graph G is perfect if and only if neither G nor its complement contains an odd hole. An important aspect of perfect graphs is that certain optimization problems, such as finding the chromatic number of a graph or the size of its largest clique, which are NP-complete in general, can be solved in polynomial time for perfect graphs. What remains open is whether it is possible to recognize perfect graphs in polynomial time. If the SPGC holds, then a polynomial time recognition algorithm for odd-hole-free graphs would imply a polynomial time recognition algorithm for perfect graphs.The project will focus on developing decomposition techniques that can be applied to solving the above mentioned problems. The power of decomposition is that it allows us to understand complex structures by breaking them down into simpler ones. Once these simpler structures are understood, this knowledge is propagated back to the original structure by understanding how their composition behaves. The use of decomposition in combinatorial theory is relatively new, but given the success It had in solving some of the difficult problems, such as recognition of regular matroids, max-flow min-cut matroids, balanced matrices and even-hole-free graphs, further understanding of decomposition techniques is bound to have an important impact on the field.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.leeds.ac.uk |