EUVIMEDEUVIMED entdecken
Crossref

Maximum Partial List H‐Coloring on P5‐Free Graphs in Polynomial Time

Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh, Roohani Sharma, Meirav Zehavi

Journal of Graph Theory · 02.08.2026

DOI: 10.1002/jgt.70107 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 02.08.2026. Verfasst von Daniel Lokshtanov und 4 weiteren Autor:innen. Die Arbeit nennt 7 Literaturangaben. Gefördert von: Institute for Basic Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this article we show that Maximum Partial List ‐ Coloring is polynomial‐time solvable on ‐free graphs for every fixed graph . In particular, this implies that Maximum ‐ Colorable Subgraph is polynomial‐time solvable on ‐free graphs. This answers an open question from Agrawal, Lima, Lokshtanov, Rzążewski, Saurabh, and Sharma [SODA 2024]. This also improves the ‐time algorithm for Maximum Partial ‐ Coloring , where is the size of the largest clique in , by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [SIDMA 2021], to polynomial‐time algorithm (independent of the maximum clique size of the graph).

Förderung

  • Institute for Basic Science

Zitieren

APA

Lokshtanov, D., Rzążewski, P., Saurabh, S., Sharma, R., & Zehavi, M. (2026). Maximum Partial List H‐Coloring on P5‐Free Graphs in Polynomial Time. Journal of Graph Theory. https://doi.org/10.1002/jgt.70107

Vancouver

Lokshtanov D, Rzążewski P, Saurabh S, Sharma R, Zehavi M. Maximum Partial List H‐Coloring on P5‐Free Graphs in Polynomial Time. Journal of Graph Theory. 2026. doi:10.1002/jgt.70107

BibTeX
@article{Lokshtanov2026,
  author = {Lokshtanov, Daniel and Rzążewski, Paweł and Saurabh, Saket and Sharma, Roohani and Zehavi, Meirav},
  title = {Maximum Partial List H‐Coloring on P5‐Free Graphs in Polynomial Time},
  journal = {Journal of Graph Theory},
  year = {2026},
  doi = {10.1002/jgt.70107}
}
Kostenlos starten →