Source-linked AI summary
Deciding k-colourability of $P_5$-free graphs in polynomial time
Chính T. Hoàng, Marcin Kamiński, Vadim Lozin, J. Sawada, X. Shu
TL;DR
The paper addresses whether fixed-k colourability remains tractable for P5-free graphs despite the NP-hardness of computing their chromatic number. It develops a recursive list-colouring algorithm based on dominating structures and dependency removal, proving polynomial-time solvability for every fixed k and producing a colouring when one exists.
Problem
Computing the chromatic number of a P5-free graph is NP-hard, while the complexity of deciding k-colourability for fixed k was unresolved.
Method
The algorithm branches over colourings of a dominating clique or P3, expresses subproblems as restricted list-colouring instances, and recursively removes dependencies between fixed sets.
Results
For every fixed integer k, restricted k-list colouring and k-colourability of P5-free graphs can be decided in polynomial time.
Takeaways & Limitations
The result establishes polynomial-time k-colourability for P5-free graphs for every fixed k, and the algorithm returns a valid colouring when one exists.
Takeaways & Limitations
The approach does not settle whether P7-free graphs can be 3-coloured in polynomial time.
Abstract
from arXiv · showhide
The problem of computing the chromatic number of a $P_5$-free graph is known to be NP-hard. In contrast to this negative result, we show that determining whether or not a $P_5$-free graph admits a $k$-colouring, for each fixed number of colours $k$, can be done in polynomial time. If such a colouring exists, our algorithm produces it.
1 Introduction
The paper studies k-colourability in P5-free graphs, a class where chromatic-number computation is NP-hard but fixed-k colourability had remained unresolved. It presents a polynomial-time algorithm for every fixed k that also constructs a colouring when one exists.
- Motivation: k-COLOURABILITY is central and difficult: it is NP-complete in general and remains hard in several restricted graph classes.Polynomial-time algorithms are known for some classes, including perfect graphs and bounded-degree graphs.
- Graph classes: P_t-free graphs are hereditary graph classes defined by excluding an induced path on t vertices.Their colouring complexity varies substantially with t and k.
- Prior work: For P5-free graphs, the complexity of k-COLOURABILITY was unresolved for general fixed k, despite known results for several nearby cases.Known results included polynomial-time solvability for P4-free graphs and unresolved cases for t = 5, 6, 7, apart from 3-COLOURABILITY results.
- Contribution: The paper proves that k-COLOURABILITY for P5-free graphs is solvable in polynomial time for every fixed k.The algorithm outputs a valid k-colouring whenever the answer is positive.
- Contribution: The result contrasts with the NP-hardness of computing the chromatic number of a P5-free graph.It also generalizes several previously studied special cases, including 4-COLOURABILITY for selected subclasses.
2 Background and Definitions
The background introduces graph, domination, list-colouring, and structural concepts used by the algorithm. The key structure is that every connected P5-free graph has a dominating clique or dominating P3, enabling a recursive decomposition of colouring instances.
- Basic definitions: The paper represents a graph as a simple undirected graph G = (V, E), with n vertices and m edges.For a vertex subset A, G(A) denotes the subgraph induced by A.
- Domination: A set A dominates B when every vertex in B is adjacent to at least one vertex in A.This notion supports the structural decomposition used later.
- P5-free structure: Every connected P5-free graph has either a dominating clique or a dominating P3.This structural theorem supplies the dominating set used by the algorithm.
- List colouring: The k-list colouring problem asks whether each vertex can receive a colour from its assigned list of k colours.Restricted k-list colouring limits every list to the colour set {1, 2, ..., k}.
- Recursive approach: The algorithm replaces one colouring instance with polynomially many equivalent instances whose answers are collectively equivalent to the original.It branches on possible colours for a dominating set and recursively removes dependencies between fixed vertex sets.
- Recursive approach: Naively applying the recursive replacement can produce an exponential number of colouring instances.The algorithm therefore requires a more controlled dependency-removal procedure.
3 The Algorithm
The algorithm recursively reduces k-colourability of connected P5-free graphs to restricted list-colouring instances by exploiting small dominating structures and removing dependencies between fixed sets. Two dependency-removal methods yield polynomially many subproblems and polynomial running time for fixed k.
- Algorithm overview: A connected P5-free graph is first given a dominating clique of at most k vertices or a dominating P3, whose possible k-colourings define restricted list-colouring subproblems.Vertices outside the dominating set are partitioned into fixed sets with lists of size at most k − 1.
- Algorithm overview: The algorithm replaces each colouring instance by a polynomial number of equivalent instances while removing dependencies between every pair of fixed sets.Vertices are dependent when adjacent and their colour lists intersect; after dependencies are removed, fixed sets can be coloured independently.
- 3.1 Removing the Dependencies Between Two Fixed Sets: Method I: Method I recursively colours stable-set pairs and branches on whether a dominating vertex receives a colour shared with the other set.Lemma 1 guarantees a vertex in one dependent subset adjacent to all vertices in the other, enabling each branch to reduce a colour set or remove a dependent vertex.
- 3.1 Removing the Dependencies Between Two Fixed Sets: Method I: Method I produces at most (kn)^k instances for one stable-set pair and (kn)^k5 instances for all fixed-set pairs after stable-set decompositions.The analysis combines the pairwise reductions across at most k^2 fixed-set pairs with a recursive (k−1)-colouring step.
- Complexity: The analyses establish polynomial running time: Method I has T(k) = O((kn)^k6), while Method II has T(k) = O(n^k3·4(k−1)).Theorem 3 and Corollary 1 conclude that restricted k-list colouring and k-colourability of P5-free graphs are polynomial-time solvable for fixed k.
- 3.2 Removing the Dependencies Between Two Fixed Sets: Method II: Method II partitions fixed sets into dynamic subsets representing unique colour-list subsets and processes pairs in decreasing colour-set size.Its structural analysis uses a connected P5-free graph H with a vertex adjacent to one dynamic set and nonadjacent to the other, together with Theorem 2.
4 Summary
For fixed k, P5-free graph k-colourability has a polynomial-time algorithm, advancing the broader complexity question for Pt-free graphs. Several related colouring and independence problems remain open.
- Summary: For every fixed k, k-colourability of P5-free graphs can be decided in polynomial time.The broader question concerns polynomial-time algorithms for k-colourability on Pt-free graphs with fixed k and t.
- Open problems: The complexity of 3-colouring P7-free graphs remains open.
- Open problems: The complexity of 4-colouring P6-free graphs remains open.
- Open problems: Whether k-colouring P7-free graphs is NP-complete remains an open question.
- Open problems: The complexities of MAXIMUM INDEPENDENT SET and MINIMUM INDEPENDENT DOMINATING SET on P5-free graphs are also open.