Equitable block-colorings of -decompositions of

详细信息    查看全文

• 作者：Shanhai Li^a ; ^{lsh751@163.com" class="auth_mail" title="E-mail the corresponding author} ; C.A. Rodger^b ; ^{rodgec1@auburn.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Equitable ; Colorings ; Cycle ; Decomposition
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 May 2016
• 年：2016
• 卷：339
• 期：5
• 页码：1519-1524
• 全文大小：379 K

文摘

In this paper we consider the existence of (s,p$s,p$)-equitable block-colorings of 4-cycle decompositions of K_v−F$K_v-F$, where F$F$ is a 1-factor of K_v$K_v$. In such colorings, the 4-cycles are colored with s$s$ colors in such a way that, for each vertex 46a5c15" title="Click to view the MathML source">u$u$, the 4-cycles containing 46a5c15" title="Click to view the MathML source">u$u$ are colored with p$p$ colors so that the number of such 4-cycles of each color is within one of the number of such 4-cycles of each of the other p−1$p-1$ colors. Of primary interest is settling the values of ${\chi }_p^{\prime }\left(v\right)$ and ${\bar{\chi }}_p^{\prime }\left(v\right)$, namely the least and greatest values of s$s$ for which there exists such a block-coloring of some 4-cycle decomposition of K_v−F$K_v-F$. In this paper, several general results are established, both existence and non-existence theorems. These are then used to find, for all possible values of v$v$, the values of ${\chi }_p^{\prime }\left(v\right)$ when p∈{2,3,4}$p\in \{2,3,4\}$ and a61a874ff6d94fae95d158c277aa505d">${\bar{\chi }}_2^{\prime }\left(v\right)$, and to provide good upper bounds on ${\bar{\chi }}_3^{\prime }\left(v\right)$.