论文标题
图形的着色避免了固定长度的双色路径
Coloring of Graphs Avoiding Bicolored Paths of a Fixed Length
论文作者
论文摘要
在不包含固定子图系列的任何双色副本的情况下，找到最小颜色数量的最小颜色数量的问题已得到广泛研究。最著名的例子是图形的星形和无环着色（Grünbaum，1973），分别不允许使用$ P_4 $的双色副本和周期。在本文中，我们引入了这些问题的变化，并研究了不包含固定长度的双色路径的图形的正确着色，并为所有图提供了一般边界。 $ p_k $ - 颜色无向图$ g $的颜色是$ g $的适当顶点着色，因此，$ g，$，$，$ g，$的$ p_k $的双色副本和$ p_k $ coloring $ g $所需的最低颜色数量称为$ p_k $ p_k $ p_k $ p_k $ chromation $ g，$ g，$ g，$ g，$ n ye $ n of s y n of s_ n n of s_ n n of s_ n n n s s_（g）s_（s_）。 $ s_k（g）$，尤其是，对于任何图形$ g $，最高度$ d \ geq 2，$ k \ geq4，$ $ $ $ s_k（g）= o（d^{\ frac {k-1} {k-1} {k-2}}）。 $ k = 5,6。$
The problem of finding the minimum number of colors to color a graph properly without containing any bicolored copy of a fixed family of subgraphs has been widely studied. Most well-known examples are star coloring and acyclic coloring of graphs (Grünbaum, 1973) where bicolored copies of $P_4$ and cycles are not allowed, respectively. In this paper, we introduce a variation of these problems and study proper coloring of graphs not containing a bicolored path of a fixed length and provide general bounds for all graphs. A $P_k$-coloring of an undirected graph $G$ is a proper vertex coloring of $G$ such that there is no bicolored copy of $P_k$ in $G,$ and the minimum number of colors needed for a $P_k$-coloring of $G$ is called the $P_k$-chromatic number of $G,$ denoted by $s_k(G).$ We provide bounds on $s_k(G)$ for all graphs, in particular, proving that for any graph $G$ with maximum degree $d\geq 2,$ and $k\geq4,$ $s_k(G)=O(d^{\frac{k-1}{k-2}}).$ Moreover, we find the exact values for the $P_k$-chromatic number of the products of some cycles and paths for $k=5,6.$
