EUVIMEDEUVIMED entdecken
Crossref

Maximum List r-Colorable Induced Subgraphs in $$kP_3$$-Free Graphs

Esther Galby, Paloma T. Lima, Andrea Munaro, Amir Nikabadi

Algorithmica · 2026-12 · 88 (6)

DOI: 10.1007/s00453-026-01410-7 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithmica, online erschienen am 05.10.2026. Verfasst von Esther Galby und 3 weiteren Autor:innen. Die Arbeit nennt 27 Literaturangaben. Gefördert von: The Independent Research Fund Denmark.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We show that, for every fixed positive integers r and k, Max-Weight Listr-Colorable Induced Subgraph admits a polynomial-time algorithm on kP3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$kP_3$$\end{document}-free graphs. This problem is a common generalization of Max-Weight Independent Set, Odd Cycle Transversal and Listr-Coloring, among others. Our result has several consequences. First, it implies that, for every fixed r≥5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r \ge 5$$\end{document}, assuming P≠NP\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{P}\ne \textsf{NP}$$\end{document}, Max-Weight Listr-Colorable Induced Subgraph is polynomial-time solvable on H-free graphs if and only if H is an induced subgraph of either kP3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$kP_3$$\end{document} or P5+kP1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_5+kP_1$$\end{document}, for some k≥1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 1$$\end{document}. 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 Listr-Coloring on kP3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$kP_3$$\end{document}-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 Listr-Coloring and provide polynomial-time algorithms on kP3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$kP_3$$\end{document}-free graphs for every fixed integers r, k, and d≥6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d \ge 6$$\end{document}.

Förderung

  • The Independent Research Fund Denmark

Zitieren

APA

Galby, E., Lima, P. T., Munaro, A., & Nikabadi, A. (2026). Maximum List r-Colorable Induced Subgraphs in $$kP_3$$-Free Graphs. Algorithmica, 88(6). https://doi.org/10.1007/s00453-026-01410-7

Vancouver

Galby E, Lima PT, Munaro A, Nikabadi A. Maximum List r-Colorable Induced Subgraphs in $$kP_3$$-Free Graphs. Algorithmica. 2026;88(6). doi:10.1007/s00453-026-01410-7

BibTeX
@article{Galby2026,
  author = {Galby, Esther and Lima, Paloma T. and Munaro, Andrea and Nikabadi, Amir},
  title = {Maximum List r-Colorable Induced Subgraphs in $$kP_3$$-Free Graphs},
  journal = {Algorithmica},
  year = {2026},
  volume = {88},
  number = {6},
  doi = {10.1007/s00453-026-01410-7}
}
Kostenlos starten →