Algorithmic Graph Theory

点击翻译按钮获取中文摘要

The main objectives of this research proposal are the design of efficient optimization algorithms for a number of graph classes and the study of their structures. These graphs in most cases have structures that can be exploited to design efficient algorithms for recognition and optimization. One key idea is graph decomposition which is a technique that decomposes a graph into "basic graphs" using certain graph operations. Graph decomposition may lead to tractable instances of generally intractable problems by virtue of defining width parameters, such as tree-widths and clique-widths, which for some restricted but rich classes of graphs can be bounded. Examples of graph classes that we will study are odd-hole-free graphs, and even-hole-free graphs. A significant number of works has been done on odd-hole-free graphs. Scott and Seymour solved a well known conjecture of Gyarfas that these graphs are chi-bounded. We propose to study the conjecture, posed by the author and C. McDiarmid, that odd-hole-free graphs are 2-divisible. A solution to this conjecture would give a significantly better bound on the chromatic number of odd-hole-free graphs. We also propose to study the conjecture that an even-hole-free graph has its clique-width bounded by a function of its clique number. This conjecture implies k-Colorability is polynomial-time solvable for even-hole-free graphs for every fixed k. The general graph coloring problem has spawned numerous variations and sub-problems, among them questions about whether an L-free graph, that is a graph that does not contain induced subgraphs from a set L of given graphs, can be colored in polynomial time. Answering such questions reveals much about the underlying structure of these graphs, and this in turn can impact applications of graph theory to such fields as circuit layout and channel assignment. There has been keen interest in coloring graphs whose forbidden list L contains graphs with four vertices. Results in the literature have reduced this problem to three outstanding classes: {4K1, claw}, {4K1, claw, co-diamond}, and {4K1,C4}. We will study these three open problems in this research proposal. Another graph coloring problem, which has received considerable attention recently, we would like to study is the complexity of coloring graphs without induced Pt, where Pt is the chordless path on t vertices.