Algorithmic Graph Theory

本研究建议的主要目标是为一些图类设计有效的优化算法，并研究它们的结构。在大多数情况下，这些图的结构可以用来设计有效的识别和优化算法。其中一个关键思想是图分解，这是一种使用某些图操作将图分解为“基本图”的技术。图分解可以通过定义宽度参数（如树宽度和树宽度）来解决一般难以解决的问题，对于某些受限但丰富的图类，这些宽度参数可以是有界的。我们将要研究的图类的例子是无奇洞图和无偶洞图。关于无奇洞图的研究已经取得了很多成果。Scott和Seymour解决了Gyarfas的一个著名猜想，即这些图是chi-有界的。本文拟研究作者和C. McDiarmid证明了无奇洞图是2-可分的。这个猜想的一个解决方案将给出一个显着更好的边界上的奇洞-免费图的色数。我们还提出了一个猜想，即一个偶无洞图的团宽度是由它的团数的一个函数所限定的。 这一猜想意味着对于任意固定的k，偶数无洞图的k-可染性是多项式时间可解的。一般的图着色问题已经产生了许多变化和子问题，其中的问题是关于L-自由图，即不包含来自给定图的集合L的导出子图的图，是否可以在多项式时间内着色。 对这些问题的研究揭示了这些图的基本结构，这反过来又会影响图论在电路布局和通道分配等领域的应用。禁止列表L中含有四个顶点的图的着色问题一直受到人们的关注。在文献中的结果已经减少了这个问题的三个突出类：{4K 1，爪}，{4K 1，爪，co-diamond}，和{4K 1，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.