2012/11/22 by Petros A. Petrosyan, Petrosyan, Petros A. · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #cs.DM #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.48550/arxiv.1211.5311
10 pages
arxiv created 2012/11/22 · openalex publication_date 2012/11/22 · arxiv updated 2012/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is called a complete k-partite (k≥ 2) graph if its vertices can be partitioned into k independent sets V1,...,Vk such that each vertex in Vi is adjacent to all the other vertices in Vj for 1≤ i<j≤ k. A complete k-partite graph G is a complete balanced k-partite graph if |V1| = |V2| =... = |Vk|. An edge-coloring of a graph G with colors 1,...,t is an interval t-coloring if all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. A graph G is interval colorable if G has an interval t-coloring for some positive integer t. In this paper we show that a complete balanced k-partite graph G with n vertices in each part is interval colorable if and only if nk is even. We also prove that if nk is even and (k-1)n≤ t≤ ((3/2)k-1)n-1, then a complete balanced k-partite graph G admits an interval t-coloring. Moreover, if k=p2q, where p is odd and q∈ ℕ, then a complete balanced k-partite graph G has an interval t-coloring for each positive integer t satisfying (k-1)n≤ t≤ (2k-p-q)n-1.