Grant: Discovery Grants Program - Individual

This research proposal is generally about algorithmic aspects of graph theory with three particular themes: optimization algorithms, certifying algorithms and structured graph theory. Four classical optimization problems on graphs require finding: an optimal coloring, an optimal clique cover, a largest clique and a largest stable set. We will attempt to solve the problems on restricted classes of graphs such as graphs without odd holes, or without induced paths of prescribed lengths. On the class of graphs without induced paths of prescribed lengths, these problems are a good way to introduce undergraduate and graduate students to research in algorithmic graph theory. Typically, the optimization problems are solved by establishing certain structural properties of the given graphs. A certifying algorithm is one that produces a certificate with each output that proves that it has not been compromised by an implementation bug. For example, a certifying algorithm for recognizing a planar graph G produces either a planar embedding of G, or one of the two Kuratowski graphs proving that G is not planar. Our recent polynomial-time certifying algorithm for 3-coloring a P5-free graph G produces either a 3-coloring of G, or a subgraph of G that is clearly not 3-colorable. We will continue our investigation for restricted graphs with larger chromatic number. In structured graph theory, one studies graphs with certain restriction such as the condition of not containing another graph as induced subgraphs. A conjecture of Erdos and Hajnal states that if a graph G does not contain a finite graph H as induced subgraph, then G has a clique or stable set of size polynomial in the number of vertices of G, where the degree of the polynomial depends only on H. We will study a family of such conjectures.