Graph Colouring for Restricted Inputs

背景资料：图是由顶点（也称为节点）和顶点之间的链接（称为边）组成的网络，边表示涉及顶点对的关系。图着色问题是用尽可能少的整数（称为颜色）标记图的顶点，使得没有两个相邻的顶点是相同的颜色。图着色是数学和计算机科学中的一个重要概念，因为它的许多应用领域跨越学科界限，并且它在计算难度研究中用作基准问题。图着色的著名应用包括地图着色，作业或时间表调度，寄存器分配，碰撞数据或交通流，频率分配和模式matching.Research Aims：由于图着色问题是计算困难的一般，这是自然的限制输入到特殊的图形类。通过利用图的结构，我们希望找到新的有效的算法，为特殊的图类，否则，获得新的棘手的结果。通过这种方式，我们可以确定计算困难的原因，这将增加我们对如何处理更一般输入的理解;这个更大的目标是我们潜在的一般动机。特别是，我们考虑类的模式免费的图形，也就是说，那些具有一些禁止模式。“无模式”的概念涵盖了大量研究得很好的图类，例如遗传图类（例如，二分图，弦图）和次闭图类（例如，平面图）。模式取决于将一个图转换为另一个图时允许的操作。这样的操作的示例是顶点删除、边删除、边收缩和顶点分解。我们要解决的重要问题是：1。哪些无模式图允许有效的着色算法？我们能根据模式获得完整的复杂性分类吗？2.）的情况。对于某些类型的模式，计算难度和效率之间是否存在二分法？为什么或为什么不？3.）第三章我们能否将所得结果推广到更一般的着色问题，如预着色扩展、列表着色、图同态和在线着色？方法：为了回答上述问题，我们将采用以下方法：1.确定所考虑的图类的有用的结构属性（例如，与图的所有其他顶点相邻的一小组顶点）;2.）证明了临界子图（图中与属性相关的部分）可以被有效地检测出来;3.）以每一种可能的方式（使用蛮力）对临界子图的顶点着色;4.）检查是否有一个部分着色（\precolourings”）可以扩展到整个图的着色，通过从其预着色的邻居强加给顶点的颜色列表中为未着色部分中的每个顶点分配颜色。要应用这种大纲4阶段方法，需要深入了解特定的图结构（对于步骤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).