Anagram-Free Graph Colouring
Anagram-Free Graph Colouring
复制标题
无字谜图形着色
DOI：
--
复制
发表时间：
2016
影响因子：
0.7
通讯作者：
D. Wood
中科院分区：
文献类型：
--
作者：
Tim E. Wilson;D. Wood
字谜词是 $WP$ 形式的单词，其中 $W$ 是非空单词，$P$ 是 $W$ 的排列。我们研究无字谜图着色并给出色数的界限。阿隆等人。 (2002)询问无字谜色数是否受最大次数函数的限制。我们通过构造最大度数为 3 和无界无字谜色数的图来否定地回答这个问题。我们还根据半径和路径宽度证明了树的无字谜色数的上限和下限。最后，我们探索边缘着色和 $k$-anagram-free 着色的扩展。
An anagram is a word of the form $WP$ where $W$ is a non-empty word and $P$ is a permutation of $W$. We study anagram-free graph colouring and give bounds on the chromatic number. Alon et al. (2002) asked whether anagram-free chromatic number is bounded by a function of the maximum degree. We answer this question in the negative by constructing graphs with maximum degree 3 and unbounded anagram-free chromatic number. We also prove upper and lower bounds on the anagram-free chromatic number of trees in terms of their radius and pathwidth. Finally, we explore extensions to edge colouring and $k$-anagram-free colouring.