© Wuhan University 2025

0 Introduction

All the graphs considered in this paper are finite, simple and undirected. We adopt the terminology and notation defined in Ref. [1] for any terms and symbols not explicitly defined here.

A proper conflict-free $k$-coloring (PCF $k$-coloring) of a graph is a proper $k$-coloring in which each non-isolated vertex has a unique color that appears exactly once in its open neighborhood. A graph is PCF $k$-colorable if it admits a proper conflict-free $k$-coloring. The minimum $k$ such that $G$ is PCF $k$-colorable is called the PCF chromatic number of $G$, denoted by ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(G)$. Let $\varphi$ be a PCF coloring of a graph $G$. We denote the color on the vertex $v\in V(G)$ as $\varphi (v)$ and its unique color as ${\varphi }^{*}(v)$.

The concept of PCF coloring was introduced by Fabirici et al^[2]. They proved that a planar graph has a PCF $\mathrm{8}$-coloring and constructed a planar graph with no PCF $\mathrm{5}$-coloring. This implies the upper bound of PCF chromatic number of planar graphs is between $\mathrm{6}$ and $\mathrm{8}$.

Caro et al^[3] investigated PCF coloring further. They determined the PCF chromatic number for several well-studied graph classes, including trees, cycles, hypercubes and subdivision of complete graphs. In particu- lar, they put forward the following conjecture.

Conjecture 1^[3] If $G$ is a connected graph of maximum degree $∆\ge \mathrm{3}$, then ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(G)\le ∆+\mathrm{1}$.

A linear coloring of a graph is a proper coloring where each pair of color classes induces a union of disjoint paths. Liu and Yu^[4] showed the following theorem.

Theorem 1   For every connected graph with maximum degree at most $\mathrm{3}$, there exists a linear $\mathrm{4}$-coloring such that the neighbors of every degree-two vertex receive different colors, unless the graph is $C_{\mathrm{5}}$ or $K_{\mathrm{3,3}}$.

By the definition of linear coloring and Theorem 1, a connected graph with maximum degree $\mathrm{3}$ is PCF $\mathrm{4}$-colorable, unless the graph is $K_{\mathrm{3,3}}$. And it is not difficult to give $K_{\mathrm{3,3}}$ a PCF $\mathrm{4}$-coloring. Thus a special case in Conjecture 1 can be derived easily and stated as follows.

Theorem 2   A connected graph with maximum degree $\mathrm{3}$ is PCF $\mathrm{4}$-colorable.

The complete subdivision of a graph $G$, denoted by $S(G)$, is a graph obtained from $G$ by subdividing each edge in $E(G)$ exactly once. Caro et al^[3] showed that ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(S(K_n))=n$ holds for $n\ge \mathrm{3}$. Additionally, they provided an upper bound on ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(S(G))$ when $G$ has a $\mathrm{1}$-factor. In Ref. [5], the authors presented the following proposition without a proof.

Proposition 1^[5] For any graph $G$, let $S(G)$ be the complete subdivision of $G$, then ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(S(G))\le \mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{5},\chi (G)\}$.

Brook's Theorem states that $\chi (G)\le ∆+\mathrm{1}$ for a connected graph $G$ with maximum degree $∆$, where equality holds if and only if $G$ is a complete graph or an odd cycle. The following theorem follows from Theorem 2 and Proposition 1.

Theorem 3   If $G$ is a connected graph with maximum degree $∆\ge \mathrm{3}$, then ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(S(G))\le ∆+\mathrm{1}$.

More results about PCF coloring of graphs are in Refs. [6-17]. We give a new shorter proof of Theorem 2 in Section 1 and proofs of Proposition 1 and Theorem 3 in Section 2.

1 Proof of Theorem 2

Lemma 1   For a connected graph $G$ on at least $\mathrm{6}$ vertices, if $G$ has an edge $e\in E(G)$such that $G-e$ has exactly one component isomorphic to $C_{\mathrm{5}}$ and $G-V(C_{\mathrm{5}})$ is PCF $\mathrm{4}$-colorable, then $G$ is also PCF $\mathrm{4}$-colorable.

Proof   Let $e=u{v}_{\mathrm{1}}$ be the edge such that $G-e$ has exactly one component isomorphic to $C_{\mathrm{5}}$ and $V(C_{\mathrm{5}})=\{v_{\mathrm{1}},v_{\mathrm{2}},v_{\mathrm{3}},v_{\mathrm{4}},v_{\mathrm{5}}\}$. And let $\varphi$ be a PCF $\mathrm{4}$-coloring of $G-V(C_{\mathrm{5}})$. Assign $v_{\mathrm{1}}$ a color not in $\{\varphi (u),{\varphi }^{*}(u)\}$. Next assign $v_{\mathrm{2}}$ and $v_{\mathrm{5}}$ the same color not in $\{\varphi (v_{\mathrm{1}}),\varphi (u)\}$. Finally, assign $v_{\mathrm{3}}$ and $v_{\mathrm{4}}$ the remaining two colors not in $\{\varphi (v_{\mathrm{1}}),\varphi (v_{\mathrm{2}})\}$. We obtain a PCF $\mathrm{4}$-coloring of $G$.

A set $H$ of seven graphs is given in Fig.1. For each graph in $H$, we give a PCF $\mathrm{4}$-coloring, i.e., they are all PCF $\mathrm{4}$-colorable. These graphs are useful in the following proof. In the following, we give the proof of Theorem 2.

Fig. 1 $\mathit{H}=\{{\mathit{H}}_{\mathrm{1}},{\mathit{H}}_{\mathrm{2}},{\mathit{H}}_{\mathrm{3}},{\mathit{H}}_{\mathrm{4}},{\mathit{H}}_{\mathrm{5}},{\mathit{H}}_{\mathrm{6}},{\mathit{H}}_{\mathrm{7}}\}$

Proof of Theorem 2   Let $H$ be a counterexample with the minimum number of vertices. We shall complete the proof by several claims.

Claim 1 $H$ has no $\mathrm{1}$-vertex.

Suppose $H$ has a $\mathrm{1}$-vertex $v$. If $H-v\cong C_{\mathrm{5}}$, then $H\cong H_{\mathrm{1}}$. By Fig.1, $H$ is PCF $\mathrm{4}$-colorable. If $H-v\ncong C_{\mathrm{5}}$, then by the choice of $H$, $H-v$ admits a PCF $\mathrm{4}$-coloring $\varphi$. Let u be the neighbor of $v$ in $H$. By assigning a color other than $\varphi (u)$ and ${\varphi }^{*}(u)$ to $v$, we obtain a PCF 4-coloring of $H$. It is a contradiction.

Recall that an $l$-thread means a path on at least $l$ vertices of degree 2 in a graph. Note that if a graph has no $l$-thread, then it has no $(l+\mathrm{1})$-thread.

Claim 2 There is no 3-thread in $H$.

Suppose $H$ has a 3-thread $xuvwy$ where $d(u)=d(v)=d(w)=\mathrm{2}$. By the choice of $H$, $H-\{u,v,w\}$ admits a PCF 4-coloring $\varphi$. Let

$C=\{\varphi (x),{\varphi }^{*}(x),\varphi (y),{\varphi }^{*}(y)\}$

Note that $\mathrm{2}\le |C|\le \mathrm{4}$.

If $|C|=\mathrm{4}$, color $u,v,w$ by $\varphi (y),{\varphi }^{*}(y),\varphi (x)$, respectively. We obtain a PCF 4-coloring of $H$.

If $|C|=\mathrm{3}$, assign $u$ a color in $\{\varphi (y),{\varphi }^{*}(y)\}\backslash \{\varphi (x),{\varphi }^{*}(x)\}$, $v$ the remaining color and $w$ a color in $\{\varphi (x),{\varphi }^{*}(x)\}\backslash \{\varphi (y),{\varphi }^{*}(y)\}$. We obtain a PCF 4-coloring of $H$.

If $|C|=\mathrm{2}$, consider $y$. If $d(y)=\mathrm{2}$, it is easy to replace $\varphi (y)$ such that $|C|=\mathrm{3}$. If $d(y)=\mathrm{3}$, assign $u$ a color not in $\{\varphi (x),{\varphi }^{*}(x)\}$, $v$ a color not in $\{\varphi (x),\varphi (u),\varphi (y)\}$ and $w$ a color not in $\{\varphi (u),\varphi (v),\varphi (y)\}$. We obtain a PCF 4-coloring of $H$.

Claim 3 Any two 2-vertices are not adjacent in $H$.

Suppose that there are two adjacent 2-vertices $v$ and $w$ in $H$. We consider two cases as follows.

Case 1 $v$ and $w$ have a common neighbor.

Let $N(v)\bigcap N(w)=\{z\}$. By Claim 2, $d(z)=\mathrm{3}$. Let $N(z)=\{v,w,z_{\mathrm{1}}\}$. By the choice of $H$, $H-v-w$ admits a PCF 4-coloring $\varphi$. Using two colors distinct from $\varphi (z)$ and $\varphi (z_{\mathrm{1}})$ to color $v$ and $w$ respectively, we obtain a PCF 4-coloring of $H$. It is a contradiction.

Case 2 $v$ and $w$ have no common neighbors.

Let $N(v)\backslash \{w\}=\{u\}$ and $N(w)\backslash \{v\}=\{x\}$. By Claim 2, $d(u)=d(x)=\mathrm{3}$.

Consider $H-v-w$ in two subcases according to its connectivity.

Subcase 1 $H-v-w$ is connected.

If $H-v-w\cong C_{\mathrm{5}}$, then $H\cong H_{\mathrm{2}}$ or $H\cong H_{\mathrm{3}}$. By Fig.1, H is PCF 4-colorable.

If $H-v-w\ncong C_{\mathrm{5}}$, then by the choice of $H$, $H-v-w$ has a PCF 4-coloring $\varphi$. Assign $w$ a color different from $\varphi (x)$ and $\varphi (u)$ and $v$ a color not in $\{\varphi (u),\varphi (w),\varphi (x)\}$. Thus, a PCF 4-coloring of $H$ is obtained.

Subcase 2 $H-v-w$ is disconnected.

Clearly, $H-v-w$ has exactly two components. If both components are isomorphic to $C_{\mathrm{5}}$, then $H\cong H_{\mathrm{5}}$. Again, $H$ is PCF 4-colorable.

If one component is $C_{\mathrm{5}}$ and the other is not, then $H-V(C_{\mathrm{5}})$ is PCF 4-colorable.

By Lemma 1, $H$ is PCF 4-colorable.

If no component of $H-v-w$ is $C_{\mathrm{5}}$, then by the choice of $H$, $H-v-w$ has a PCF 4-coloring, which can be extended to a PCF 4-coloring of $H$ in the same way in Subcase 1.

Claim 4 Each 3-vertex has at most two 2-neighbors in $H$.

By Claim 1, each vertex is of degree 2 or 3 in $H$. Suppose for the contrary that $H$ has a 3-vertex $u$ adjacent to three 2-vertices $v,w$ and $x$. Let

$N(v)=\{u,v_{\mathrm{1}}\},N(w)=\{u,w_{\mathrm{1}}\}$and $N(x)=\{u,x_{\mathrm{1}}\}$.

By Claim 3, we have $d(v_{\mathrm{1}})=d(w_{\mathrm{1}})=d(x_{\mathrm{1}})=\mathrm{3}$. We consider $H-\{u,v,w,x\}$.

Case 3 $H-\{u,v,w,x\}$ is connected.

If $H-\{u,v,w,x\}\cong C_{\mathrm{5}}$, then $H\cong H_{\mathrm{6}}$. By Fig.1, $H$ is PCF 4-colorable.

If $H-\{u,v,w,x\}\ncong C_{\mathrm{5}}$, then by the choice of $H$, $H-\{u,v,w,x\}$ admits a PCF 4-coloring $\varphi$. Assign $u$ a color distinct from $\varphi (v_{\mathrm{1}}),\varphi (w_{\mathrm{1}})$ and $\varphi (x_{\mathrm{1}})$. Next, assign $v$ a color distinct from $\varphi (u)$ and $\varphi (v_{\mathrm{1}})$. Then assign $w$ a color not in $\{\varphi (u),\varphi (v),\varphi (w_{\mathrm{1}})$ and $x$ a color not in $\{\varphi (u),\varphi (v),\varphi (x_{\mathrm{1}})$. The resulting coloring is a PCF 4-coloring of $H$.

Case 4 $H-\{u,v,w,x\}$ is disconnected.

By Claim 3, a 5-cycle in $H$ has at least three 3-vertices, which implies that no component of $H-\{u,v,w,x\}$ is $C_{\mathrm{5}}$. Then by the choice of $H$, $H-\{u,v,w,x\}$ has a PCF 4-coloring, which can be extended to a PCF 4-coloring of H in the same way as we did in the previous case.

Claim 5 $H$ has no 2-vertices.

Suppose that $H$ has a 2-vertices $u$ and $N(u)=\{v,w\}$. By Claim 1 and Claim 3, we know that $d(v)=d(w)=\mathrm{3}$. Let $N(v)=\{ux,y\}$. By Claim 4, $v$ has at most two 2-neighbors. We consider two cases as follows.

Case 5 $v$ has just one 2-neighbors $u$.

Consider $H-u-v$.

Subcase 3 $H-u-v$ is connected.

If $H-u-v\cong C_{\mathrm{5}}$, then $H\cong H_{\mathrm{7}}$. By Fig.1, $H$ is PCF 4-colorable.

If $H-u-v\ncong C_{\mathrm{5}}$, then by the choice of $H$, $H-u-v$ admits a PCF 4-coloring $\varphi$. Assign $v$ a color distinct from $\{\varphi (x),\varphi (y),\varphi (w)\}$ and assgin $u$ a color not in $\{\varphi (w),\varphi (v),\varphi (x)\}$. The resulting coloring is a PCF 4-coloring of $H$.

Subcase 4 $H-u-v$ is disconnected.

Again, by Claim 3, no component of $H-u-v$ is $C_{\mathrm{5}}$. Then by the choice of $H$, $H-u-v$ has a PCF 4-coloring, which can be extended to a PCF 4-coloring of $H$ in the same way in the previous subcase.

Case 6 $v$ has exactly two 2-neighbors.

With loss of generality, let $d(x)=\mathrm{2},d(y)=\mathrm{3}$ and $N(x)=\{v,x_{\mathrm{1}}\}$. By Claim 3, $d(x_{\mathrm{1}})=\mathrm{3}$. Consider $H-\{u,v,x\}$.

Subcase 5 $H-\{u,v,x\}$ is connected.

By Claim 4, $x_{\mathrm{1}},w$ and $y$ have at most two 2-neighbors. If $H-\{u,v,x\}\cong C_{\mathrm{5}}$, then $H\cong H_{\mathrm{4}}$. Again $H$ is PCF 4-colorable.

If $H-\{u,v,x\}\ncong C_{\mathrm{5}}$, then by the choice of $H$, $H-\{u,v,x\}$ admits a PCF 4-coloring $\varphi$. Assign $v$ a color not in $\{\varphi \left(w\right),\varphi \left(y\right),\varphi \left(x_{\mathrm{1}}\right)\}$. Next, assign $u$ a color not in $\{\varphi (w),\varphi (v),\varphi (y)\}$ and assign $x$ a color not in $\{\varphi (x_{\mathrm{1}}),\varphi (v),\varphi (y)$. Thus we obtain a PCF 4-coloring of $H$.

Subcase 6 $H-\{u,v,x\}$ is disconnected.

By Claim 3, no component of $H-\{u,v,x\}$ is $C_{\mathrm{5}}$. Then by the choice of $H$, $H-\{u,v,x\}$ has a PCF 4-coloring, which can be extended to a PCF 4-coloring of $H$ in the same way as we did in the previous subcase.

Next, we shall show that $H$ is PCF 4-colorable to get a contradiction. By Claim 1 and Claim 5, $H$ is 3-regular. We consider two cases as follows.

Claim 6 $H$ has a triangle.

Assume that $uvw$ is a triangle in $H$. Let $N\left(u\right)\backslash \left\{v,w\right\}=\left\{u_{\mathrm{1}}\right\},N\left(v\right)\backslash \left\{u,w\right\}=$$\{v_{\mathrm{1}}\}$ and $N(w)\backslash \{u,v\}=\{w_{\mathrm{1}}\}$. Note that $H-v$ has exactly three 2-vertices. Thus $H-v$ has no component isomorphic to $C_{\mathrm{5}}$. By the choice of $H$, $H-v$ admits a PCF 4-coloring $\varphi$, which can be extended to a PCF 4-coloring of $H$ after assign $v$ a color not in $\{\varphi (u),\varphi (w),\varphi (v_{\mathrm{1}})\}$. Thus $H$ is PCF 4-colorable.

Claim 7 $H$ is triangle-free.

Pick an edge $uv\in E(H)$, and let $N(u)\backslash \{v\}=\{u_{\mathrm{1}},u_{\mathrm{2}}\}$ and $N(v)\backslash \{u\}=$$\{v_{\mathrm{1}},v_{\mathrm{2}}\}$. Note that $H-u-v$ has exactly four 2-vertices. Thus $H-u-v$ has no component isomorphic to $C_{\mathrm{5}}$. By the choice of $H$, $H-u-v$ admits a PCF 4-coloring $\varphi$.

If $\varphi (v_{\mathrm{1}})=\varphi (v_{\mathrm{2}})$, assign $u$ a color not in $\{\varphi (u_{\mathrm{1}}),\varphi (u_{\mathrm{2}}),\varphi (v_{\mathrm{1}})\}$, and then assign $v$ a color not in $\{\varphi (v_{\mathrm{1}}),\varphi (u),\varphi (u_{\mathrm{1}})\}$. Thus, we can get a PCF 4-coloring of $H$.

If $\varphi (v_{\mathrm{1}})\ne \varphi (v_{\mathrm{2}})$, assign $v$ a color not in $\{\varphi (v_{\mathrm{1}}),\varphi (v_{\mathrm{2}}),\varphi (u_{\mathrm{1}})\}$, and then assign $u$ a color not in $\{\varphi (u_{\mathrm{1}}),\varphi (u_{\mathrm{2}}),\varphi (v)$. The resulting coloring is also a PCF 4-coloring of $H$.

This proof is completed.

2 Proofs of Proposition 1 and Theorem 3

Proof of Proposition 1   We may assume that $G$ has no isolated vertex. Let $M$ be a maximum matching of $G$. And let $U$ be the set of unsaturated vertices of $G$ under $M$. Thus, for each vertex $u\in U$, there exists a neighbor $u\text{'}$ saturated by $M$ in $G$. We now give a PCF coloring of $S(G)$ using at most $\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{5},\chi (G)\}$ as follows.

Take a proper coloring $\varphi$ of $G$ using colors $\{\mathrm{1},\cdots ,\chi (G)\}$. Color the vertex inserting into the edge $uv$ of $M$ with a color distinct from $\varphi (u)$ and $\varphi (v)$. This color is chosen to be the unique color (i.e. ${\varphi }^{*}(u)$ and ${\varphi }^{*}(v)$) on the neighborhoods of $u$ and $v$. Next, for each $u\in U$, color the vertex inserting into $uu\text{'}$ with a color distinct from $\varphi (u),\varphi (u\text{'})$ and ${\varphi }^{*}(u\text{'})$. This color is chosen to be the unique color (i.e. ${\varphi }^{*}(u)$) on the neighborhoods of $u$. For an edge $xy\in E(G)\backslash (M\bigcup \{uu\text{'}:u\in U\})$, color the vertex inserting into $xy$ by a color not in $\{\varphi (x),{\varphi }^{*}(x),\varphi (y),{\varphi }^{*}(y)\}$. Thus, a PCF coloring of $S(G)$ is obtained using $\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{5},\chi (G)\}$ colors.

Proof of Theorem 3   Let $G$ be a connected graph with maximum degree $∆\ge \mathrm{3}$.

If $∆=\mathrm{3}$, then $∆(S(G))=\mathrm{3}$. By Theorem 2, ${\mathrm{\chi }}_{\mathrm{p}\mathrm{c}\mathrm{f}}(S(G))=\mathrm{4}=∆+\mathrm{1}$.

If $∆\ge \mathrm{4}$, then by Brook's Theorem, $\chi (G)\le ∆+\mathrm{1}$. By Proposition 1, ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(S(G))\le \mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{5},\chi (G)\}\le ∆+\mathrm{1}$. The proof is completed.

References

All Figures

	Fig. 1 $\mathit{H}=\{{\mathit{H}}_{\mathrm{1}},{\mathit{H}}_{\mathrm{2}},{\mathit{H}}_{\mathrm{3}},{\mathit{H}}_{\mathrm{4}},{\mathit{H}}_{\mathrm{5}},{\mathit{H}}_{\mathrm{6}},{\mathit{H}}_{\mathrm{7}}\}$
In the text