Research Area 3 Mathematical Sciences/Modeling and Complex Systems - Coloring Perfect Graphs
Abstract
This project will investigate new methods for proving the existence of and developing resulting efficient computational coloring algorithms over perfect graphs. This project will attempt to develop the concept of "extreme decompositions" by finding a decomposition that splits the graph into two parts, one of which no longer admits a decomposition of the same type and is therefore simpler than the original graph. There is reason to hope that this approach will result in a polynomial-time coloring algorithm for perfect graphs that do not admit a balanced partition. It will then attempt to show that the blocks of the decomposition do not admit a balanced skew-partition. If an iterative method can be devised, it may be able to the whole graph can be efficiently colored.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 06, 2017
- Source ID
- W911NF1610404
Entities
People
- Maria Chudnovsky
Organizations
- Army Contracting Command
- Princeton University
- United States Army