Graph Colouring Problems with Restricted Inputs

图是由节点和节点之间的链接组成的网络，称为边，表示涉及节点对的关系。最初的图着色问题是用尽可能少的整数(称为颜色)来标记图的结点，使得相邻的两个结点没有相同的颜色。图着色是数学和计算机科学中的一个重要概念，因为它的许多应用领域跨越了学科边界，并被用作计算难度研究的基准问题。图着色的著名应用包括地图着色、作业或时间表调度、寄存器分配、冲突数据或交通流、频率分配和模式匹配。由于图着色问题通常在计算上很困难，因此将输入限制在特殊的图类中是很自然的。通过利用图的结构，我们期望为特殊的图类找到新的高效算法，否则将获得新的难解结果。通过这种方式，我们可以确定计算困难的原因，这将增加我们对如何处理更一般输入的理解；这个更大的目标是我们潜在的一般动机。特别地，我们考虑了一类无模式的图类，即那些被禁止的模式所刻画的图类。“无模式”的概念捕获了大量研究良好的图类，例如遗传图类(例如，二部图、弦图)和次闭合图类(例如，平面图)。我们将解决的重要问题是：哪些无模式的图允许高效的着色算法？我们能根据模式获得完整的复杂性分类吗？对于某些类型的模式，是否存在计算难度和效率之间的二分法？为什么或者为什么不？我们能否将已有的结果推广到更一般的染色问题，如预染色扩张、列表染色、非圈染色、星染色、图同态和在线染色？

A graph is a network of nodes and links between nodes called edges that represent a relationship involving pairs of nodes. The original Graph Colouring problem is that of labelling the nodes of a graph with the smallest possible number of integers (called colours) so that no two neighbouring nodes are identically coloured. Graph Colouring is an important concept in Maths 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. 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). Important questions we will address are: Which pattern-free graphs allow efficient colouring algorithms? Can we obtain full complexity classifications based on the pattern? Do dichotomies between computational hardness and efficiency even exist for certain types of pattern? Why or why not? Can we extend obtained results to more general colouring problems such as precolouring extension, list colouring, acyclic colouring, star colouring, graph homomorphisms and on-line colouring?