On the Complexity of Colouring Antiprismatic Graphs
- PDF / 1,624,423 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 222 Views
On the Complexity of Colouring Antiprismatic Graphs Myriam Preissmann1 · Cléophée Robin1,2 · Nicolas Trotignon2 Received: 27 October 2019 / Accepted: 4 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract A graph G is prismatic if for every triangle T of G, every vertex of G not in T has a unique neighbour in T. The complement of a prismatic graph is called antiprismatic. The complexity of colouring antiprismatic graphs is still unknown. Equivalently, the complexity of the clique cover problem in prismatic graphs is not known. Chudnovsky and Seymour gave a full structural description of prismatic graphs. They showed that the class can be divided into two subclasses: the orientable prismatic graphs, and the non-orientable prismatic graphs. We give a polynomial time algorithm that solves the clique cover problem in every non-orientable prismatic graph. It relies on the the structural description and on later work of Javadi and Hajebi. We give a polynomial time algorithm which solves the vertex-disjoint triangles problem for every prismatic graph. It does not rely on the structural description. Keywords Coloring · Algorithm · Claw-free graph · Dichotomy
1 Introduction We consider undirected simple graphs (no multiple edge, no loop). A k-colouring of a graph G is a function f from V(G) to {1, … , k} such that for all uv ∈ E(G) , f (u) ≠ f (v) . The colouring problem is the problem whose input is a graph G and whose output is a k-colouring of G such that k is minimum. The colouring problem is NP-hard and is the object of much attention. In particular, its complexity is known for several classes of graphs.
* Nicolas Trotignon nicolas.trotignon@ens‑lyon.fr Myriam Preissmann myriam.preissmann@grenoble‑inp.fr Cléophée Robin cleophee.robin@grenoble‑inp.fr 1
CNRS, Grenoble INP, G‑SCOP, Univ. Grenoble Alpes, 38000 Grenoble, France
2
EnsL, UCBL, CNRS, LIP, Univ Lyon, 69342 Lyon Cedex 07, France
13
Vol.:(0123456789)
Algorithmica
When H is a graph, a graph G is H-free if it does not contain any induced subgraph isomorphic to H. When H is a set of graphs, G is H-free if G is H-free for all H ∈ H . We denote by Pk the path on k vertices and by Ck the cycle on k vertices. When G and H are graphs, we denote by G + H their disjoint union. When G is a graph and k is an integer, we denote by kG the disjoint union of k copies of G. We denote by Kk the complete graph on k vertices. We denote by Kk,l the complete bipartite graph with one side of the bipartition of size k and the other side of size l. A stable set is a set of vertices that are pairwise non-adjacent. A clique is a set of vertices that are pairwise adjacent. Král’ et al. [8] proved the following dichotomy: the colouring problem for H-free graphs is polynomial time solvable if H is an induced subgraph of P4 or an induced subgraph of K1 + P3 , and NP-hard otherwise. This motivated the systematic study of the colouring problem restricted to {H1 , H2 }-free graphs for all possible pairs of graphs H1 , H2 , or even to H-free g
Data Loading...
