CS Paper Radar

Complexity and algorithms for proper conflict-free coloring in graphs

Dinabandhu Pradhan, Vaishali Sharma

cs.DM math.CO ·submitted 2026-08-11 12:52 UTC · v2

Abstract

A proper conflict-free (PCF) $k$-coloring of a graph $G$ is a proper $k$-coloring such that there exists a color that appears exactly once in the neighborhood of every non-isolated vertex $v\in V(G)$. The PCF chromatic number, denoted by $χ_{pcf}(G)$, is the least integer $k$ such that there exists a PCF $k$-coloring of $G$. Given a graph $G$ and a positive integer $k$, PCF $k$-COLORABILITY is to decide whether $G$ admits a PCF $k$-coloring. Ahn et al. [Discrete Appl. Math. 377 (2025) 10-17] proved that PCF $k$-COLORABILITY is NP-complete for bipartite graphs. We strengthen this result by proving that PCF $k$-COLORABILITY is NP-complete for perfect elimination bipartite graphs, which is a proper subclass of bipartite graphs. We also show that the PCF chromatic number of a graph cannot be approximated within $O(n^{1-\varepsilon})$ unless P=NP, for any $\varepsilon>0$. On the positive side, we provide linear-time algorithms for PCF $k$-COLORABILITY in block graphs, proper interval graphs, chain graphs, and pseudo-split graphs. We show that $χ_{pcf}(G)\leq ω(G)+1$ for block graphs, proper interval graphs, and pseudo-split graphs (except $C_5$), and we characterize all graphs for which the equality holds.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Classical and Parameterized Complexity of Strong Odd Coloring

cs.DM math.CO ·2026-10-01 ·Dinabandhu Pradhan, Vaishali Sharma, Shaily Verma
theory similarity 0.84
Abstract

A strong odd $k$-coloring of a graph $G$ is a proper $k$-coloring such that every color appearing in the neighborhood of a non-isolated vertex appears an odd number of times. The minimum $k$ for which $G$ admits a strong odd $k$-coloring is the \emph{strong odd chromatic number}, denoted by $χ_{\text{so}}(G)$, of $G$. Given a graph $G$ and an integer $k$, \textsc{strong odd $k$-colorability} problem asks whether $G$ admits a strong odd $k$-coloring. It is known that STRONG ODD $k$-COLORABILITY is NP-complete in general graphs. In this paper, we prove that the problem is NP-complete on perfect elimination bipartite graphs for $k\geq3$, which is a subclass of bipartite graphs. Furthermore, we show that $χ_{\text{so}}(G)$ is inapproximable within a factor of $O(n^{\frac{1}{2}-\varepsilon})$ for every $\varepsilon>0$. On the positive side, we obtain a linear time algorithm to compute an optimal strong odd coloring for block graphs. From a parameterized perspective, we present an FPT algorithm for STRONG ODD $k$-COLORABILITY when parameterized by treewidth. Moreover, we show that the problem cannot be solved in time $(k-\varepsilon)^{\texttt{tw}}n^{O(1)}$ for every $k\geq3$ and $\varepsilon>0$ when parameterized by treewidth under SETH. Furthermore, we show that STRONG ODD $k$-COLORABILITY does not admit a polynomial kernel when parameterized by feedback vertex set. Lastly, we prove that STRONG ODD $k$-COLORABILITY is W[1]-hard when parameterized by clique-width.

0.05

Proper Conflict-Free Coloring on Structured Graph Classes: Bounds, Exact Algorithms, and Hardness

cs.DM math.CO ·2026-11-02 ·Kamal Santra
theory similarity 0.78
Abstract

A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a neighbor whose color appears exactly once in its open neighborhood. We study this coloring on chordal and ordered bipartite graph classes. For well-partitioned chordal graphs, we prove the tight bound $ω(G)\leq\pcf(G)\leqω(G)+1$ and give an $O(n^2)$ construction from a partition tree. Every assignment of lists of at least $ω(G)+1$ colors also admits a PCF coloring that respects the lists. Deciding whether $ω(G)$ colors suffice is NP-complete, even when the partition tree is a star. This also proves NP-completeness on chordal graphs when the number of colors is part of the input. For interval graphs, we prove that lists of size $ω(G)+1$ always suffice, improving the previous ordinary-coloring bound of $ω(G)+2$. We use matchings to characterize when $ω(G)$ colors suffice and give an endpoint algorithm taking $2^{O(ω(G)^2)}n^{O(1)}$ time. We also characterize the exact value when the clique number is at most three and give a linear-time algorithm from sorted interval endpoints. For biconvex graphs, we prove a tight five-color bound and give a direct exact algorithm taking $O(n^{33})$ time. For bipartite permutation graphs, a smaller dynamic program gives an exact $O(n^{17})$ algorithm. Finally, if a bipartite graph is convex over an ordered shore $X$, we prove the sharp bound $\pcf(G)\leq\lceil\log_2(|X|+1)\rceil+3$ and construct a coloring in linear time from the order.

0.36

Proper Conflict-Free Coloring of Undirected Path, Chordal Bipartite, and Strongly Chordal Graphs

cs.DM math.CO ·2026-11-04 ·Gautam K. Das, Kamal Santra
theory similarity 0.78
Abstract

A proper conflict-free coloring is a proper coloring in which each nonisolated vertex has a neighbor whose color occurs exactly once in its open neighborhood. We prove that deciding whether the clique number of colors suffices is NP-complete on undirected path graphs, even with a supplied representation by paths in a star. One extra color suffices on every instance in the reduction. We also prove NP-completeness on chordal bipartite graphs for every fixed palette size $k\ge4$. For strongly chordal graphs, reverse simple elimination gives a constructive upper bound of one more than the clique number. We obtain exact polynomial-time algorithms under several conditions on the maximum cliques, including when they induce a connected subtree of a clique tree. For strictly chordal graphs we characterize the optimum and construct an optimal coloring in $O(n+m)$ time, where $n$ and $m$ count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most $s$, we give an exact algorithm in $n^{2^{O(s+1)}}$ time, with no bound on the clique number.

0.12

Structural Complexity of Matching-Match: Dense and Sparse Graphs

cs.DS ·2026-09-22 ·Ilie Dumitru, Adrian Miclăuş, Alexandru Popa
theory similarity 0.76
Abstract

The Matching-Match puzzle asks whether the vertices of a fixed graph can be colored so that the multiset of color pairs induced by its edges is exactly a prescribed multiset. We study how the complexity of this realization problem depends on the host graph. On the dense side, we give a polynomial-time algorithm for complete $k$-partite graphs for every fixed number $k$ of parts, with arbitrary precoloring and an arbitrary number of colors. We prove a sharp complement-degree threshold: the problem is polynomial-time solvable when $Δ(\overline G)\le1$, but NP-complete on completely uncolored graphs already when $Δ(\overline G)=2$. This yields a dichotomy for uniform complete multipartite graphs, and connected diameter two already suffices for NP-completeness. We also prove W[1]-hardness on cographs parameterized by the number of colors. On the sparse side, completely uncolored paths and cycles admit a linear-time characterization by Euler trails and circuits, while counting feasible colorings is $\#P$-complete on both classes. Counting is nevertheless polynomial-time solvable on stars and complete graphs, even with arbitrary precoloring. A decomposition-transfer theorem yields NP-completeness already at tree-depth two. A separate path-decomposition reduction gives a maximum-degree threshold between one and two for completely uncolored disconnected host graphs with unrestrictedly many colors. Components with at most two edges are tractable, while a disjoint union of $P_4$'s is NP-complete. Finally, precoloring restores tractability in several cases: star forests are polynomial when every center is precolored, and two broad precoloring regimes on length-two spiders are polynomial even when the number of colors is unbounded.

0.21

Claw-free perfect graphs are chromatic-choosable

cs.DM math.CO ·2026-10-31 ·Suchismita Mishra, Narayanan Narayanan, Umesh Shankar
theory similarity 0.76
Abstract · 33 pages, 8 figures

We prove that every claw-free perfect graph $G$ satisfies $\ch(G)=χ(G)=ω(G)$. More strongly, if $S$ is a clique of simplicial vertices of $G$ and $k\geω(G)$, every proper precoloring of $S$ extends to a proper coloring of $G$ from arbitrary lists of size $k$ on $V(G)\setminus S$. The proof has three coloring steps: a mixed-list theorem for cobipartite graphs, a precoloring-extension theorem for elementary graphs built on Galvin's kernel method and a homogeneous-pair exchange argument, and a polynomial method (Combinatorial Nullstellensatz) argument for graphs of interval type in which a Vandermonde factor is transferred across each incomplete pair. The three coloring steps are assembled along the structure theorems of Chvátal--Sbihi, Maffray--Reed and Chudnovsky--Seymour, using double clique cutsets for composition. As a consequence, every perfect line graph is chromatic-choosable, recovering the theorem of Peterson and Woodall. Our precoloring extension theorem also resolves a conjecture posed by Chudnovsky and Seymour.

0.24

Parameterized complexity of $k$-Coloring in graphs with no long induced paths

cs.DS ·2026-08-18 ·Paweł Rzążewski
theory similarity 0.76
Abstract

We study the parameterized complexity of (List) $k$-Coloring in $H$-free graphs, where $H$ is a linear forest, that is, a disjoint union of paths. First, considering $k$ as the parameter, we establish the following: * For any $s \geq 0$, List $k$-Coloring in $(P_4+sP_1)$-free graphs is fixed-parameter tractable (FPT). * $k$-Coloring is W[1]-hard in $2P_2$-free graphs. The second result settles, in a strong form, a long-standing open problem posed by Hoàng, Kamiński, Lozin, Sawada, and Shu [Algorithmica, 2010]. Next, we prove that $k$-Coloring is NP-hard in $(P_4+P_2)$-free graphs. These three findings, together with known results from classical, non-parameterized complexity, yield a complete complexity classification of $k$-Coloring and List $k$-Coloring in $H$-free graphs, parameterized by $k$, into the cases: FPT, XP but W[1]-hard, and paraNP-hard. We also prove that $3$-Coloring is W[1]-hard in $P_t$-free graphs when parameterized by $t$. This answers a question of Golovach, Johnson, Paulusma, and Song [Journal of Graph Theory, 2017]. Finally, as a byproduct of our algorithm for List $k$-Coloring in $(P_4+sP_1)$-free graphs, we show that, for every fixed $s$ and $k$, there are only finitely many $(P_4+sP_1)$-free minimal obstructions to $k$-colorability. This settles a conjecture of Cameron, Hoàng, and Sawada [Disc. Appl. Math., 2022] and completes the dichotomy concerning the finiteness of the family of vertex-$k$-critical $H$-free graphs for every graph $H$ and every $k$.

0.20

Minimum Label $k$-Cut on Planar Graphs: Complexity and Color Structure

cs.DS ·2026-10-29 ·Yuanhao Wang, Wei Wang
theory similarity 0.75
Abstract

Minimum Label $k$-Cut asks for a minimum-size set of colors such that deleting all edges of these colors leaves at least $k$ connected components. We study how the structure of the underlying graph and its color classes affects the complexity of this problem. Regarding fixed-parameter tractability with respect to $k$ on simple planar graphs, we prove that the problem is W[1]-hard, even when the underlying graph is a cactus graph and each color appears at most twice. Furthermore, for cactus graphs in which every color class is connected, we establish a complexity boundary in terms of the maximum monochromatic degree: when this degree is at most two, an optimal solution can be found in $O(Nk^2)$ time, where $N$ is the input size, with no restriction on color frequency or the number of blocks spanned by a color; allowing the maximum monochromatic degree to increase to three already makes the decision version NP-complete. Finally, we prove that the problem remains W[1]-hard parameterized by $k$ on fan graphs, even when every color class is an induced path. These results show that bounding color frequency does not suffice to eliminate parameterized hardness. They also establish a monochromatic-degree boundary for connected colors on cactus graphs and identify complexity barriers to extending this tractable case to outerplanar graphs.

0.16

Mutual-visibility k-colouring is NP-complete for every fixed diameter

cs.DM cs.CCmath.CO ·2026-10-31 ·Siddhesh Chaubal
similarity 0.72
Abstract · 9 pages, 1 figure. v2: extended to any fixed number k of colours; new title

A mutual-visibility set in a graph G is a set S of vertices such that any two vertices of S are connected by a shortest path with no internal vertex in S, and the mutual-visibility chromatic number $χ_μ(G)$ is the minimum number of mutual-visibility sets needed to partition V(G). Babu, Di Stefano and Lakshmanan showed that it is NP-complete to decide whether $χ_μ(G)\le 2$ for graphs of diameter four. We show that the problem remains NP-complete for graphs of diameter d, for every fixed $d\ge2$; diameter two is the smallest diameter for which the problem is non-trivial. More generally, for all fixed $k\ge2$ and $d\ge2$, it is NP-complete to decide whether $χ_μ(G)\le k$ for graphs of diameter d. The proof rests on a reformulation of $χ_μ(G)\le 2$ for diameter-two graphs as the 2-colourability of an associated hypergraph, and on a reduction from 2-colourability of 3-uniform hypergraphs without short cycles.

0.24