Interval edge-colorings of complete graphs

详细信息    查看全文

• 作者：H.H. Khachatrian^a ; ^{hrant.khachatrian@ysu.am" class="auth_mail" title="E-mail the corresponding author} ; P.A. Petrosyan^a ; ^b ; ^{pet_petros@ipia.sci.am" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Edge-coloring ; Interval edge-coloring ; Complete graph ; 1-factorization
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 September 2016
• 年：2016
• 卷：339
• 期：9
• 页码：2249-2262
• 全文大小：1396 K

文摘

An edge-coloring of a graph G$G$ with colors 1,2,…,t$1,2,\dots ,t$ is an interval  t$t$-coloring   if all colors are used, and the colors of edges incident to each vertex of G$G$ are distinct and form an interval of integers. A graph G$G$ is interval colorable   if it has an interval t$t$-coloring for some positive integer t$t$. For an interval colorable graph G$G$, W(G)$W\left(G\right)$ denotes the greatest value of t$t$ for which G$G$ has an interval t$t$-coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of W(K_2n)$W\left(K_{2n}\right)$ is known only for n≤4$n\le 4$. The second author showed that if n=p2^q$n=p{2}^q$, where p$p$ is odd and q$q$ is nonnegative, then W(K_2n)≥4n−2−p−q$W\left(K_{2n}\right)\ge 4n-2-p-q$. Later, he conjectured that if n∈N$n\in \mathbb{N}$, then W(K_2n)=4n−2−⌊log₂n⌋−‖n₂‖$W\left(K_{2n}\right)=4n-2-\lfloor {log}_{2}n\rfloor -\Vert n_2\Vert$, where ‖n₂‖$\Vert n_2\Vert$ is the number of 1’s in the binary representation of n$n$.

In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on W(K_2n)$W\left(K_{2n}\right)$ and determine its exact values for n≤12$n\le 12$.