2024/09/26 by Petrosyan, Petros A., Khachatrian, Hrant H., Tananyan, Hovhannes G.
#05C15 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.18088
An interval t-coloring of a graph G is a proper edge-coloring with colors 1,…,t such that the colors on the edges incident to every vertex of G are colored by consecutive colors. A graph G is called interval colorable if it 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, we denote by w(G) and W(G) the minimum and maximum number of colors in an interval coloring of a graph G, respectively. In this paper we present some new sharp bounds on W(G\square H) for graphs G and H satisfying various conditions. In particular, we show that if G,H∈ \mathfrakN and H is an r-regular graph, then W(G\square H)≥ W(G)+W(H)+r. We also derive a new upper bound on W(G) for interval colorable connected graphs with additional distance conditions. Based on these bounds, we improve known lower and upper bounds on W(C_2n1\square C_2n2\square⋯ \square C_2nk) for k-dimensional tori C_2n1\square C_2n2\square⋯ \square C_2nk and on W(K_2n1\square K_2n2\square⋯ \square K_2nk) for Hamming graphs K_2n1\square K_2n2\square⋯ \square K_2nk, and these new bounds coincide with each other for hypercubes. Finally, we give several results on interval colorings of Fibonacci cubes Γn.