2012/01/31 by Petros A. Petrosyan, Petrosyan, Petros A., Hrant Khachatrian +4
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1202.0023
18 pages
arxiv created 2012/01/31 · openalex publication_date 2012/01/31 · arxiv updated 2012/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Let \mathfrakN be the set of all interval colorable graphs. For a graph G∈ \mathfrakN, the least and the greatest values of t for which G has an interval t-coloring are denoted by w(G) and W(G), respectively. In this paper we first show that if G is an r-regular graph and G∈ \mathfrakN, then W(G\square Pm)≥ W(G)+W(Pm)+(m-1)r (m∈ ℕ) and W(G\square C2n)≥ W(G)+W(C2n)+nr (n≥ 2). Next, we investigate interval edge-colorings of grids, cylinders and tori. In particular, we prove that if G\square H is planar and both factors have at least 3 vertices, then G\square H∈ \mathfrakN and w(G\square H)≤ 6. Finally, we confirm the first author's conjecture on the n-dimensional cube Qn and show that Qn has an interval t-coloring if and only if n≤ t≤ (n(n+1))/(2).