Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter

DOI10.1016/J.TCS.2022.07.034MaRDI QIDQ6383756arXivFDO

Authors Barnaby Martin, Daniël Paulusma, Siani Smith

Publication date 23 November 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2022.07.034

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.CCcs.DMcs.DSmath.CO

Abstract: For a fixed integer, the $k$-Colouring problem is to decide if the vertices of a graph can be coloured with at most $k$ colours for an integer $k$, such that no two adjacent vertices are coloured alike. A graph $G$ is $H$-free if $G$ does not contain $H$ as an induced subgraph. It is known that for all $kgeq3$, the $k$-Colouring problem is NP-complete for $H$-free graphs if $H$ contains an induced claw or cycle. The case where $H$ contains a cycle follows from the known result that the problem is NP-complete even for graphs of arbitrarily large fixed girth. We examine to what extent the situation may change if in addition the input graph has bounded diameter.

This page was built for publication: Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6383756)