2026-08-04T07:59:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15454 2024-03-06T10:55:19Z ddc:004 open_access

Partitioning H-Free Graphs of Bounded Diameter Brause, Christoph Golovach, Petr Martin, Barnaby Paulusma, Daniël Smith, Siani vertex partitioning problem H-free diameter complexity dichotomy A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ideal testbed for such a complexity study. However, if the forbidden graph H contains a cycle or claw, then these problems often stay NP-complete. A recent complexity study (MFCS 2019) on the k-Colouring problem shows that we may still obtain tractable results if we also bound the diameter of the H-free input graph. We continue this line of research by initiating a complexity study on the impact of bounding the diameter for a variety of classical vertex partitioning problems restricted to H-free graphs. We prove that bounding the diameter does not help for Independent Set, but leads to new tractable cases for problems closely related to 3-Colouring. That is, we show that Near-Bipartiteness, Independent Feedback Vertex Set, Independent Odd Cycle Transversal, Acyclic 3-Colouring and Star 3-Colouring are all polynomial-time solvable for chair-free graphs of bounded diameter. To obtain these results we exploit a new structural property of 3-colourable chair-free graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christoph Brause and Petr Golovach and Barnaby Martin and Daniël Paulusma and Siani Smith 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.21 urn:nbn:de:0030-drops-154543 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.21 eng https://creativecommons.org/licenses/by/4.0/legalcode