Algorithmic Graph Theory

该研究方案的主要目标是为若干图类设计有效的优化算法并研究它们的结构。在大多数情况下，这些图具有可用于设计有效的识别和优化算法的结构。其中一个关键思想是图分解，这是一种使用特定的图操作将图分解成“基本图”的技术。通过定义宽度参数，例如树宽和团宽，图分解可以导致一般难以处理的问题的易于处理的实例，对于某些受限制但丰富的图类来说，这些参数可以是有界的。我们将研究的图类的例子有无奇洞图和无偶洞图。关于无奇洞图的研究已经做了大量工作。Scott和Seymour解决了Gya fas的一个著名猜想，即这些图是X有界的。我们建议研究作者和C.McDiarmid提出的猜想，即无奇洞图是2-可除的。这个猜想的一个解决方案将给出一个关于无奇洞图的色数的一个明显更好的界。我们还建议研究这样一个猜想，即无偶洞图的团宽度由其团数的函数限定。这个猜想表明，对于任意固定的k，无偶洞图的k-可染性是多项式时间可解的。*一般的图染色问题已经产生了无数的变种和子问题，其中一个问题是：一个L无图，即不包含给定图的L集的导出子图的图，是否可以在多项式时间内着色。回答这些问题揭示了这些图的基本结构，这反过来又会影响图论在电路布局和通道分配等领域的应用。图的禁止列表L包含四个顶点的图的着色一直是人们热衷的问题。文献中的结果已将这个问题归结为三个突出的类：{4K1，爪子}，{4K1，爪子，共钻}，和{4K1，C4}。我们将在这份研究提案中研究这三个悬而未决的问题。另一个最近备受关注的图染色问题是无诱导图的上色问题，这里的图是t个顶点上的无弦路径。

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.