| Abstrakt: |
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 it has an interval t -coloring for some positive integer t. For an interval colorable graph G , the least and the greatest values of t for which G has an interval t -coloring are denoted by w (G) and W (G). Let G be a graph with vertex set V (G) = { u 1 , ... , u m } , m ≥ 2 , and let h m = (H i) i ∈ { 1 , ... , m } be a sequence of vertex-disjoint with V (H i) = { x 1 (i) , ... , x n i (i) } , n i ≥ 1. The generalized lexicographic products G [ h m ] of G and h m is a simple graph with vertex set ∪ i = 1 m V (H i) , in which x p (i) is adjacent to x q (j) if and only if either u i = u j and x p (i) x q (i) ∈ E (H i) or u i u j ∈ E (G). In this paper, we obtain several sufficient conditions for the generalized lexicographic product G [ h m ] to have interval colorings. We also present some sharp bounds on w (G [ h m ]) and W (G [ h m ]) of G [ h m ]. [ABSTRACT FROM AUTHOR] |
