P_m□P_n的奇染色和正常无冲突染色

Odd Coloring and Proper Conflict-Free Coloring of P_m□P_n

摘要: 图的染色理论在模式识别、生物信息、社交网络和电力网络上有重要的应用。对于图$G$ 的一个点染色$\phi :V\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ ，若满足对任意非孤立点$v\in V\left(G\right)$ ，都存在$c\in \left\{1,2,\cdots ,k\right\}$ 使得$\left|{\phi }^{-1}\left(c\right)\cap N\left(v\right)\right|$ 是一个奇数，则称$\phi$ 是图$G$ 的一个奇$k$ -染色。特别地，若$\left|{\phi }^{-1}\left(c\right)\cap N\left(v\right)\right|=1$ ，则称$\phi$ 是图$G$ 的一个正常无冲突$k$ -染色。图$G$ 的奇(正常无冲突)色数是使图$G$ 有一个奇(正常无冲突) $k$ -染色的$k$ 的最小值，记作${\chi }_o\left(G\right)\left({\chi }_{pcf}\left(G\right)\right)$ 。本文研究笛卡尔乘积图的奇染色和正常无冲突染色，确定了$P_m$ 和$P_n$ 的笛卡尔乘积图的奇色数和正常无冲突色数，确定了奇色数的上界，丰富了图的染色理论，为实践应用提供了理论指导。

Abstract: The coloring theory of graphs has important applications in pattern recognition, biological information, social networks and power networks. For a vertex coloring $\phi :V\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ of a graph G, it is called an odd k-coloring of G if for each non-isolated vertex $v\in V\left(G\right)$ , there exist $c\in \left\{1,2,\cdots ,k\right\}$ such that $\left|{\phi }^{-1}\left(c\right)\cap N\left(v\right)\right|$ is odd. Especially, it is called a proper conflict-free k-coloring of G when $\left|{\phi }^{-1}\left(c\right)\cap N\left(v\right)\right|=1$ . The odd (proper conflict-free) chromatic number of a graph G, denoted by ${\chi }_o\left(G\right)\left({\chi }_{pcf}\left(G\right)\right)$ , is the minimum k such that G has an odd (proper conflict-free) k-coloring. In this paper, we study the odd coloring and proper conflict-free coloring of cartesian product graph, determine the odd chromatic number and PCF chromatic number of cartesian product graph of $P_m$ and $P_n$ , and determine the upper bound of odd chromatic number, which enriches the coloring theory of graphs and provides theoretical guidance for practical application.