Graph Colouring for Restricted Inputs

背景：图是一个由顶点（也称为节点）和顶点之间的链接（称为边）组成的网络，代表了涉及顶点对的关系。图着色问题是用尽可能少的整数（称为颜色）标记图的顶点，以便没有两个相邻顶点的颜色相同。图着色是数学和计算机科学中的一个重要概念，因为它具有跨越学科边界的许多应用领域，并且在计算硬度研究中用作基准问题。众所周知的图形着色应用包括地图着色、作业或时间表调度、寄存器分配、碰撞数据或交通流、频率分配和模式匹配。研究目的：由于图着色问题通常计算困难，因此将输入限制为特殊的图类是很自然的。通过利用图结构，我们期望为特殊的图类找到新的有效算法，或者获得新的难解性结果。通过这种方式，我们可以确定计算硬度的原因，这将增加我们对如何处理更一般输入的理解；这个更大的目标是我们潜在的总体动机。特别地，我们考虑无模式图的类别，即那些以某些禁止模式为特征的图。“无模式”的概念捕获了大量经过充分研究的图类，例如遗传图类（例如，二部图，弦图）和小闭图类（例如，平面图）。该模式取决于将一个图转换为另一个图时所允许的操作。这些操作的例子有顶点删除、边删除、边收缩和顶点溶解。我们将讨论的重要问题有：1)哪些无模式图形允许有效的着色算法？我们能否基于模式获得完全的复杂度分类？对于某些类型的模式，计算硬度和效率之间是否存在二分法？为什么或为什么不？我们是否可以将得到的结果推广到更一般的着色问题，如预着色扩展、列表着色、图同态和在线着色？方法:为了回答上述问题，我们将采用以下方法：1.)确定正在考虑的图类的一个有用的结构属性(例如，少量其他图的顶点相邻的顶点);2)表明,关键子图(图形与属性相关的一部分)可以检测到e地;3)颜色重要子图的顶点(使用蛮力)在每一个可能的方式;4)检查是否一个局部色素(\ precolourings”)可以扩展到整个图colouringof带有部分分配每个顶点的颜色从自然色彩强加给它的顶点precoloured邻居。要应用这种四阶段方法，需要深入了解特定的图形结构（步骤1-2）和设计新的着色技术来解决预着色扩展和列出着色问题（步骤3-4）。我们注意到，还需要制定新的办法。这样做的一个原因是，后两个问题对于考虑的特定图类来说可能很难计算。我们参考调查[1,2]了解无模式图的方法和最先进的描述（对于许多无模式图类，完全复杂性分类仍然是开放的）的详细信息。

Background: A graph is a network of vertices (also called nodes) and links between vertices called edges that represent a relationship involving pairs of vertices. The Graph Colouring problem is that of labelling the vertices of a graph with the smallest possible number of integers (called colours) so that no two neighbouring vertices are identically coloured. Graph Colouring is an important concept in Mathematics and Computer Science due both to its many application areas crossing disciplinary boundaries and to its use as a benchmark problem in research into computational hardness. Well-known applications of Graph Colouring include map colouring, job or timetable scheduling, register allocation, colliding data or traffic streams, frequency assignment and pattern matching.Research Aims: As the Graph Colouring problem is computationally hard in general, it is natural to restrict the input to special graph classes. By exploiting the graph structure we expect to find new efficient algorithms for special graph classes or else to obtain new intractability results. In this way we can identify the reasons for computational hardness, which will increase our understanding of how to deal with more general inputs; this bigger goal is our underlying general motivation. In particular we consider classes of pattern-free graphs, that is, those that are characterized by some forbidden pattern. The notion of being "pattern-free" captures a large number of well-studied graph classes, such as hereditary graph classes (for example, bipartite graphs, chordal graphs) and minor-closed graph classes (for example, planar graphs). The pattern depends upon the operations allowed when transforming one graph into another. Examples of such operations are vertex deletion, edge deletion, edge contraction and vertex dissolution. Important questions we will address are:1.) Which pattern-free graphs allow efficient colouring algorithms?Can we obtain full complexity classifications based on the pattern?2.) Do dichotomies between computational hardness and efficiency even exist for certaintypes of pattern? Why or why not?3.) Can we extend obtained results to more general colouring problems such as precolouringextension, list colouring, graph homomorphisms and on-line colouring?Methodology: To answer the above questions we will apply the following approach:1.) determine a useful structural property of the graph class under consideration (forexample, a small set of vertices adjacent to all other vertices of the graph);2.) show that the critical subgraph (the part of the graph associated with the property) canbe detected e ciently;3.) colour the vertices of the critical subgraph in every possible way (using brute force);4.) check if one of the partial colourings (\precolourings") can be extended to a colouringof the whole graph by assigning each vertex in the uncoloured part a colour from a listof colours forced upon the vertex by its precoloured neighbours.To apply this outline 4-stage approach requires deep insight into specific graph structures (for steps 1-2) and the design of new colouring techniques to solve the precolouring extension and list colouring problems (for steps 3-4). We note that new approaches need to be developed as well. One reason for this is that the latter two problems may well be computationally hard for the speci fic graph class under consideration. We refer to the surveys [1,2] for details on both methodology for pattern-free graphs and a state-of-the-art description (full complexity classifications are still wide open for many pattern-free graph classes).