没有K4-图子式的图的邻点可区别全染色
平 王, 维凡 王 · Science in China Series A-Mathematics (in Chinese) · 2009
图 $G$ 的邻点可区别全染色是$G$ 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. $G$的邻点可区别全色数$\chi''_{a}(G)$是使得$G$有一个$k$-\!邻点可区别全染色的最小的整数$k$. 本文完整刻画了没有$K_4$-\!图子式的图的邻点可区别全色数. 证明了: 如果 $G$是一个满足最大度$\Delta \ge 3$且没有$K_4$-\!图子式的图, 则$\Delta+1\le \chi''_{a}(G)\le \Delta+2$, 且$\chi''_{a}(G)=\Delta+2$当且仅当$G$中含有两个相邻最大度点.