摘要
A proper conflict-free k-coloring of a graph is a proper k-coloring in which each nonisolated vertex has a color that appears ex-actly 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 χ_(pcf)(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Δ≥3,χ_(pcf)(G)≤Δ+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 max{5,x(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Δ≥3,its complete subdivision is PCF(Δ+1)-colorable.
图的一个正常无冲突k-染色是一个正常k-染色,使得任意一个非孤立点的邻点中有一种颜色只出现一次。如果一个图有一个正常无冲突k-染色,称它是正常无冲突k-可染的。图的正常无冲突色数是使得它是正常无冲突k-可染的k的最小值,记作χ_(pcf)(G)。Caro等人猜想χ_(pcf)(G)≤△+1对最大度△≥3的连通图G成立。最大度为3的连通图是正常无冲突4-可染的,是该猜想的一种情形,可由Liu和Yu的结论得到。Jiménez等人不加证明地给出图G的正常无冲突色数的上界是max{5'χ(G)}。本文中,我们给出上面两个结论新的证明,并得到对最大度△≥3的连通图,其完全剖分是正常无冲突(△+1)-可染的。
基金
Supported by the Youth Fund of Lanzhou Jiaotong University(1200061328)。
