Fractional Thue chromatic number of graphs

详细信息    查看全文

• 作者：Yaling Zhong ; Xuding Zhu ; ^{xudingzhu@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Thue chromatic number ; Fractional Thue chromatic number ; Non-repetitive colouring
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 February 2016
• 年：2016
• 卷：200
• 期：Complete
• 页码：191-199
• 全文大小：404 K

文摘

This paper introduces the concept of the fractional Thue chromatic number of graphs and studies the relation between the fractional Thue chromatic number and the Thue chromatic number. We determine the fractional Thue chromatic number of all paths, all trees with no vertices of degree two, and all cycles, except C₁₀$C_{10}$, C₁₄$C_{14}$, C₁₇$C_{17}$. As a consequence, we prove that if G$G$ is a path or a tree with no degree two vertices, then its fractional Thue chromatic number equals its Thue chromatic number. On the other hand, we show that there are trees and cycles whose fractional Thue chromatic numbers are strictly less than their Thue chromatic numbers.