CLC number: O157.5

New Proofs of Results about Proper Conflict-Free Coloring of Graphs

图的正常无冲突染色结论的新证明

¹ Department of Basic Education, Rocket Force University of Engineering, Xi'an 710025, Shaanxi, China
² Department of Mathematics, Lanzhou Jiaotong University, Lanzhou 730070, Gansu, China
³ Xi'an Qinghua Middle School, Xi'an 710038, Shaanxi, China

^† Corresponding author. E-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 12 March 2025

Abstract

A proper conflict-free k-coloring of a graph is a proper k-coloring in which each nonisolated vertex has a 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 PCF chromatic number of a graph G, denoted by ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(G)$, is the minimum $k$ such that $G$ is PCF k-colorable. Caro et al conjectured that for a connected graph G with maximum degree $\Delta \ge \mathrm{3}$, ${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}\left(G\right)\le \Delta +\mathrm{1}$. One case in this conjecture, a connected graph with maximum degree 3 is PCF 4-colorable, can be derived from the result of Liu and Yu. Jiménez et al stated that the upper bound of PCF chromatic number of a graph $G$ is $\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{5},\chi (G)\}$ without a proof. In this paper, we give new proofs of the two results above and derive that for a connected graph $G$ with maximum degree $\Delta \ge \mathrm{3}$, its complete subdivision is PCF $(∆+\mathrm{1})$-colorable.

摘要

图的一个正常无冲突$k$-染色是一个正常$k$-染色，使得任意一个非孤立点的邻点中有一种颜色只出现一次。如果一个图有一个正常无冲突$k$-染色，称它是正常无冲突$k$-可染的。图的正常无冲突色数是使得它是正常无冲突$k$-可染的$k$的最小值，记作${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}(G)$。Caro等人猜想${\chi }_{\mathrm{p}\mathrm{c}\mathrm{f}}\left(G\right)\le \Delta +\mathrm{1}$对最大度$\Delta \ge \mathrm{3}$的连通图$G$成立。最大度为3的连通图是正常无冲突$\mathrm{4}$-可染的，是该猜想的一种情形，可由Liu和Yu的结论得到。Jiménez等人不加证明地给出图$G$的正常无冲突色数的上界是$\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{5},\chi (G)\}$。本文中，我们给出上面两个结论新的证明，并得到对最大度$\Delta \ge \mathrm{3}$的连通图，其完全剖分是正常无冲突$(∆+\mathrm{1})$-可染的。