染色问题在传递图类上的计算复杂性

Graph colouring has been a central topic for more than 150 years in mathematics and computer science since the Four Colour Conjecture was introduced in 1852. The problem is not only of fundamental importance in theory but also has wide applications in such areas as scheduling, wireless communication, bioinformatics, etc. The computational complexity of the graph colouring problem enjoys a rapid growth in the past few decades due to many important results obtained by top researchers such as M. Chudnovsky and D. Paulusma. However, many fundamental problems in the area remain unsolved. In this project, we propose to study the computational complexity of graph colouring on hereditary graph classes in a systematic way, and aim to identify the boundary between NP-completeness and polynomial time solvability by designing new polynomial-time algorithms and proving new NP-completeness results. The expected outcomes of this research will solve several important open problems in the area including the computational complexity of 3-colouring graphs without an induced path, of chromatic number on graphs that do not contain two given graphs H1 and H2 as induced subgraphs, and of colouring graphs without odd holes or even holes. This will deepen our theoretical understanding of the computational complexity of graph colouring, and provide theoretical framework for potential applications of graph colouring.

图染色问题自1852年四色猜想提出以来一直是数学和计算机中的核心问题。该问题不但有极强的理论价值，还在排序、无线电通讯、生物信息学等领域有广泛应用。图染色的计算复杂性研究在过去几十年中得到了快速发展，吸引了M. Chudnovsky、D. Paulusma等学者的广泛关注，取得了一些优美的结果，但目前仍有很多重要的问题有待解决。本项目将开展图染色在传递图类上计算复杂性的系统研究，旨在通过设计该问题新的多项式时间算法和证明新的NP-完全结果，解决该领域内的几个重要公开问题，包括3-染色问题在不含一条导出路的图上、色数问题在不含给定图H1和H2的图上、染色问题在无奇洞的图和无偶洞的图上的计算复杂性，以加深对图染色计算复杂性的理解，致力于描绘该问题在传递图类上的计算复杂性面貌以及区分难易程度的界限。预期的研究成果一方面将加深对图染色计算复杂性的理论认识，另一方面会给潜在的实际应用提供理论支持。

图染色问题自1852年四色猜想提出以来一直是数学和计算机中的核心问题。该问题不但有极强的理论价值，还在排序、无线电通讯、生物信息学等领域有广泛应用。本项目已按计划完成，达到预期目标。主要研究成果如下：1）与Serge Gaspers合作，解决了Paul Erdos 上世纪80年代悬赏的公开问题以及给出了一类传递图类上色数紧的上界；2）与Serge Gaspers以及Daniel Paulusma合作，解决了色数问题在无一条路和4长圈的图上的计算复杂性的几乎完全分类；3）与Maria Chudnovsky等人合作，给出了奇圈同态问题在无一条导出路的图上的计算复杂性的初步结果；4）与Kathie Cameron和T. Karthick等人合作，给出了几类传递图类上色数紧的上界；5）与比利时Jan Goedgebeur以及南开大学组合中心史永堂教授等人合作，给出了（P5，H）-free图中k-临界图有限性的完整分类，其中H是一个4个顶点的图。