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?