Maximum List r r -Colorable Induced Subgraphs in k P 3 kP_{3} -free Graphs
Esther Galby †, Paloma T. Lima ‡, Andrea Munaro §, Amir Nikabadi ‡ · 2025
Read Maximum List r r -Colorable Induced Subgraphs in k P 3 kP_{3} -free Graphs by Esther Galby †, Paloma T. Lima ‡, Andrea Munaro §, Amir Nikabadi ‡ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00412.txt.
Introduction
Esther Galby and co-authors solve a weighted coloring problem on graphs that avoid a small forbidden pattern, in a mathematics paper from 2025. The problem asks for the heaviest set of vertices that can be colored from personal lists of allowed colors. It generalizes several classic problems, including independent sets and odd cycle cuts.
For graphs with no induced copy of a fixed number of three-vertex paths, the authors give a polynomial-time algorithm for every fixed number of colors. The result settles when the problem is easy on pattern-free graphs for five or more colors. It also advances a dichotomy for the odd cycle problem and re-proves, shortly, a known coloring result. Distance versions of the problems are handled too.
Catalog record
| CREATOR | Esther Galby †, Paloma T. Lima ‡, Andrea Munaro §, Amir Nikabadi ‡ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00412
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Maximum List r r -Colorable Induced Subgraphs in k P 3 kP_{3} -free Graphs Esther Galby †, Paloma T. Lima ‡, Andrea Munaro §, Amir Nikabadi ‡ Abstract . We show that, for every fixed positive integers r r and k k , Max-Weight List r r -Colorable Induced Subgraph admits a polynomial-time algorithm on k P 3 kP_{3} -free graphs. This problem is a common generalization of Max-Weight Independent Set , Odd Cycle Transversal and List r r -Coloring , among others. Our result has several consequences. First, it implies that, for every fixed r ≥ 5 r\geq 5 , assuming 𝖯 ≠ 𝖭𝖯 \mathsf{P}\neq\mathsf{NP} , Max-Weight List r r -Colorable Induced Subgraph is polynomial-time solvable on H H -free graphs if and only if H H is an induced subgraph of either k P 3 kP_{3} or P 5 + k P 1 P_{5}+kP_{1} , for some k ≥ 1 k\geq 1 . Second, it makes considerable progress toward a complexity dichotomy for Odd Cycle Transversal on H H -free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rzążewski, Saurabh, and Sharma [TALG 2024]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that List r r -Coloring on k P 3 kP_{3} -free graphs is polynomial-time solvable for every fixed r r and k k . We also consider two natural distance- d d generalizations of Max-Weight Independent Set and List r r -Coloring and provide polynomial-time algorithms on k P 3 kP_{3} -free graphs for every fixed integers r r , k k , and d ≥ 6 d\geq 6 . 1. Introduction A fundamental class of graph optimization problems consists in finding a maximum-weight induced subgraph satisfying a certain fixed property \Pi . Lewis and Yannakakis [ 17 ] showed that, whenever this fixed property \Pi is nontrivial and hereditary 1 1 1 A graph property \Pi is nontrivial if it is true for infinitely many graphs and false for infinitely many graphs. It is hereditary if, whenever a graph satisfies \Pi , all its induced subgraphs satisfy \Pi as well. , the corresponding problem is \mathsf{NP} -hard. In this paper, we investigate the case where \Pi is the property of being list r -colorable, leading to a meta-problem called Max-Weight List r -Colorable Induced Subgraph . In order to properly define this problem, we first require some definitions. Let G=(V,E) be a finite simple graph. A coloring of G is a mapping \phi\colon V\rightarrow\{1,2,\ldots\} that gives each vertex u\in V a color \phi(u) in such a way that, for every two adjacent vertices u and v in G , we have that \phi(u)\neq\phi(v) . For r\geq 1 , a coloring \phi of G is an r -coloring if \phi(u)\in\{1,\ldots,r\} for every u\in V , and a graph is r -colorable if it admits an r -coloring. For r\geq 1 , an r -list assignment of G is a function L\colon V\rightarrow 2^{\{1,\ldots,r\}} that assigns each vertex u\in V a list L(u)\subseteq\{1,\ldots,r\} of admissible colors for u . A coloring \phi of G respects L if \phi(u)\in L(u) for every u\in V . We are finally ready to define Max-Weight List r -Colorable Induced Subgraph , where r is a fixed positive integer. Max-Weight List r -Colorable Induced Subgraph Input: A graph G equipped with a weight function w\colon V(G)\rightarrow\mathbb{Q}_{+} , and an r -list assignment L of G . Task: Find a subset F\subseteq V(G) such that: (1) The induced subgraph G[F] admits a coloring that respects L , and (2) The weight w(F)=\sum_{v\in F}w(v) is maximum subject to the condition above. Max-Weight List r -Colorable Induced Subgraph is a common generalization of several well-known and deeply investigated \mathsf{NP} -hard problems, as we explain next. Max-Weight List r -Colorable Induced Subgraph generalizes List r -Coloring and hence r -Coloring as well, which are known to be NP -hard for all r>2 [ 16 ] . Recall that, for a fixed r\geq 1 , List r -Coloring is the problem to decide whether a given graph G with an r -list assignment L admits a coloring that respects L . By setting L(u)=\{1,\ldots,r\} for every u\in V(G) , we obtain r -Coloring . Note also that, for r_{1}\leq r_{2} , List r_{1} -Coloring is a special case of List r_{2} -Coloring . Several other NP -hard problems are special cases of Max-Weight List r -Colorable Induced Subgraph for specific values of r . For example, for r=1 , Max-Weight List r -Colorable Induced Subgraph is equivalent to Max-Weight Independent Set , which is the problem of finding a maximum-weight subset of pairwise non-adjacent vertices of an input graph G . For r=2 , Max-Weight List r -Colorable Induced Subgraph generalizes the problem of finding a maximum-weight induced bipartite subgraph of an input graph G which, by complementation, is equivalent to finding a minimum-weight subset of vertices intersecting all odd cycles in G . The latter problem is the well-known Odd Cycle Transversal . Given the hardness of Max-Weight List r -Colorable Induced Subgraph , it is natural to investigate whether the problem becomes tractable for restricted classes of inputs. The framework of hereditary graph classes (i.e., graph classes closed under vertex deletion) is particularly well suited for this type of research, where the ultimate goal is to obtain complexity dichotomies telling us for which hereditary graph classes the problem at hand can or cannot be solved efficiently (under the standard complexity assumption that \mathsf{P}\neq\mathsf{NP} ). We recall some relevant definitions. A graph G is H -free , for some graph H , if it contains no induced subgraph isomorphic to H , that is, we cannot modify G into H by a sequence of vertex deletions. For a set of graphs \{H_{1},\ldots,H_{p}\} , a graph is (H_{1},\ldots,H_{p}) -free if it is H_{i} -free for every i\in\{1,\ldots,p\} . The disjoint union G+H of graphs G and H is the graph with vertex set V(G)\cup V(H) and edge set E(G)\cup E(H) . We denote the disjoint union of k copies of G by kG and let P_{s} denote the chordless path on s vertices. It is known that, for r=2 , Max-Weight List r -Colorable Induced Subgraph admits no polynomial-time algorithm on H -free graphs unless H is a linear forest (i.e., a disjoint union of paths). Indeed, Chiarelli et al. [ 6 ] showed that its special case Odd Cycle Transversal is NP -hard on H -free graphs if H contains a cycle or a claw (the claw is the 4 -vertex star). In recent years, considerable work has been done toward classifying the complexity of Odd Cycle Transversal (and its generalizations) on graphs forbidding an induced linear forest. In Theorem 1 , we collect known results for Odd Cycle Transversal and its two generalizations Max-Weight r -Colorable Induced Subgraph and Max-Weight List r -Colorable Induced Subgraph on H -free graphs, where H is a linear forest. The problems are listed in increasing order of generality. In particular, an \mathsf{NP} -hardness result for a certain problem implies \mathsf{NP} -hardness for a more general problem. Note also that the