2026-08-17T18:30:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24508 2025-12-16T14:00:08Z ddc:004 open_access

Maximum List r-Colorable Induced Subgraphs in kP₃-Free Graphs Galby, Esther Lima, Paloma T. Munaro, Andrea Nikabadi, Amir Hereditary classes list coloring odd cycle transversal independent set We show that, for every fixed positive integers r and k, Max-Weight List r-Colorable Induced Subgraph admits a polynomial-time algorithm on kP₃-free graphs. This problem is a common generalization of Max-Weight Independent Set, Odd Cycle Transversal and List r-Coloring, among others. Our result has several consequences. First, it implies that, for every fixed r ≥ 5, assuming 𝖯 ≠ NP, Max-Weight List r-Colorable Induced Subgraph is polynomial-time solvable on H-free graphs if and only if H is an induced subgraph of either kP₃ or P₅+kP₁, for some k ≥ 1. Second, it makes considerable progress toward a complexity dichotomy for Odd Cycle Transversal on H-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rzążewski, Saurabh, and Sharma [ACM Trans. Algorithms 2025]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that List r-Coloring on kP₃-free graphs is polynomial-time solvable for every fixed r and k. We also consider two natural distance-d generalizations of Max-Weight Independent Set and List r-Coloring and provide polynomial-time algorithms on kP₃-free graphs for every fixed integers r, k, and d ≥ 6. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Esther Galby and Paloma T. Lima and Andrea Munaro and Amir Nikabadi 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.40 urn:nbn:de:0030-drops-245086 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.40 eng https://creativecommons.org/licenses/by/4.0/legalcode