On the complexity of colouring antiprismatic graphs
From MaRDI portal
Publication:6327809
DOI10.1007/S00453-020-00767-7arXiv1910.11001MaRDI QIDQ6327809FDOQ6327809
Authors: Myriam Preissmann, Cléophée Robin, Nicolas Trotignon 
Publication date: 24 October 2019
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 emph{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.
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15)
This page was built for publication: On the complexity of colouring antiprismatic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6327809)
