Algorithmic Graph Theory

本研究计划的主要目标是为许多图类设计有效的优化算法并研究它们的结构。在大多数情况下，这些图的结构可以用来设计有效的识别和优化算法。其中一个关键思想是图分解，这是一种使用特定图操作将图分解为“基本图”的技术。通过定义宽度参数（如树宽度和团宽度），图分解可能会导致一般棘手问题的易于处理的实例，对于一些受限但丰富的图类来说，这些参数是有界的。我们将学习的图类的例子是无奇孔图和无偶孔图。在无奇孔图上已经做了大量的工作。Scott和Seymour解决了Gyarfas的一个著名猜想，即这些图是chi-bounded。我们提出研究由作者和C. McDiarmid提出的关于无奇洞图是2可除的猜想。这一猜想的解将给出无奇洞图色数的一个明显更好的界。我们还研究了偶孔无图的团宽度以团数的函数为界的猜想。这个猜想意味着对于每一个固定k，对于偶孔无图，k-可色性是多项式时间可解的******一般图的着色问题已经产生了许多变体和子问题，其中关于L-自由图（即不包含给定图的集合L中的诱导子图）是否可以在多项式时间内着色的问题。回答这些问题揭示了很多关于这些图的底层结构，这反过来可以影响图论在电路布局和信道分配等领域的应用。对于禁止列表L中包含4个顶点的图的着色图，人们一直有浓厚的兴趣。文献中的结果将这个问题简化为三个突出的类别：{4K1， claw}, {4K1, claw， co-diamond}和{4K1，C4}。我们将在本研究计划中研究这三个开放性问题。另一个近年来备受关注的图着色问题，我们想要研究的是没有诱导Pt的图着色的复杂性，其中Pt是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.