It is proved that PCF-COLORABILITY is NP-complete for bipartite graphs, and linear-time algorithms for PCF-COLORABILITY are provided in block graphs, proper interval graphs, chain graphs, and pseudo-split graphs.
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 $\chi_{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 $\chi_{pcf}(G)\leq \omega(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.
For a graph $G$, a proper coloring of $G$ is called proper conflict-free if for every non-isolated vertex $u$, there is at least one color appearing exactly once in $N_G(u)$. A graph $G$ is proper conflict-free $f$-choosable if for every list assignment $L$ with $|L(v)|\ge f(v)$ for each vertex $v$, $G$ admits a proper conflict-free $L$-coloring. Recently, Kashima, \v{S}krekovski, and Xu proposed a conjecture on proper conflict-free list coloring. For a graph $G$, let $\kappa_G:V(G)\to \mathbb{N}$ be defined by \[ \kappa_G(v)= \begin{cases} 4,&\text{if } d_G(v)=2,\\[4pt] d_G(v)+1,&\text{if } d_G(v)\neq 2. \end{cases} \] They conjectured that every connected graph other than $C_5$ is proper conflict-free $\kappa_G$-choosable. In this paper, we confirm this conjecture in two classes of graphs with bounded average degree, thereby generalizing results of Kashima, \v{S}krekovski, and Xu and of Wang and Zhang. We prove that every connected graph $G\neq C_5$ with either $\operatorname{mad}(G)<\frac{12}{5}$ or $\Delta(G)\le3$ is proper conflict-free $\kappa_G$-choosable. To prove these results, we introduce a method based on systems of proper conflict-free representatives and develop a construction of auxiliary graphs that preserves the maximum average degree bound.
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular edge colorings of graphs, SIAM J. Discrete Math. 40 (2026) 897--904), which states that $\chi_k'(G)\leq k+o(k)$ for every $0_k$-graph $G$. We prove a lower bound for $0_k$-graphs with degree set $\{k,2k\}$ and a specified vertex partition. With a suitable choice of the part sizes, if the number of edges inside one part is $o(k^2)$, then $\chi_k'(G)\geq(4-2\sqrt2+o(1))k$. This gives connected bipartite and connected nonbipartite counterexamples. In particular, the same examples also disprove the earlier conjecture of Botler, Colucci, and Kohayakawa (The mod $k$ chromatic index of graphs is $O(k)$, J. Graph Theory 102 (2023) 197--200), which states that $\chi_k'(G)\leq k+C$ for some absolute constant $C$.
A graph $G$ is $k$-choosable if it has a proper coloring for every $k$-list assignment. While every $C_3$-free planar graph is $4$-choosable, some of them are not $3$-choosable, as constructed by Voigt. Hu and Zhu conjectured that if $G$ is a $C_3$-free planar graph and $X \subseteq V(G)$ induces a bipartite subgraph, then $G$ has a proper $L$-coloring whenever $|L(x)| = 3$ for $x \in X$ and $|L(v)| = 4$ for $v \in V(G) \setminus X$. As evidence, they proved the conjecture when $X$ is an independent set. We provide further evidence by proving the conjecture when the induced subgraph $G[X]$ is an induced sparse matching. This is the first result supporting the conjecture in which the set $X$ receiving smaller lists may induce a subgraph with edges.
S. Hartke, Yu-Pei Li, Joseph Pappe et al.· 0 citations
A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let $q_B(G)$ be the minimum number of colors in such a coloring. Every graph of maximum degree $\Delta$ is $K_{2,\Delta+1}$-free; hence the known $2\Delta$ bound for planar graphs with $\Delta\ge38$ (Kong et al., 2026) motivates our study of $K_{2,t}$-free planar graphs, where $t\ge2$ is an integer. We prove $q_B(G)=\Delta(G)$ when $t=2$ and $\Delta(G)\ge7$, or when $t\ge3$ and $\Delta(G)\ge14(t-1)$. For $t\ge35$, the bound $q_B(G)\le\Delta(G)+t-1$ holds regardless of $\Delta(G)$; for every $t\ge2$, it also holds when $\Delta(G)>428$. Finally, for every integer $k\ge1$, every $k$-degenerate $K_{2,t}$-free graph satisfies $q_B(G)\le\Delta(G)+(k-1)\min\{t-1,\Delta(G)\}$, with equality for $K_{k,t-1}$ when $k\ge2$ and $t-1\ge k$.
A $k$-irregular graph is a graph with maximum degree $k$ such that vertices of degree $k$ are not adjacent. A $2$-distance $k$-coloring of a graph is a coloring of the vertices using $k$ colors in which any two vertices at distance at most $2$ receive distinct colors. The $2$-distance chromatic number of $G$, denoted by $\chi_{2}(G)$, is the minimum integer $k$ such that $G$ admits a $2$-distance $k$-coloring. Zhu \cite{zhu} proved that $\chi_2(G)\leq 13$ for planar graphs with maximum degree at most $4$. We prove that for a 4-irregular planar graph $G$, we have $\chi_2(G) \leq 10$.
Sara Al Hajjar· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
