Graph Colouring Problems with Restricted Inputs

输入受限的图形着色问题

• 批准号: 2867894
• 金额: --
• 依托单位: Durham University
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2867894
• 关键词: Graph; Colouring; Problems; 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?

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