Geodesic
Interval edge colorings of some products of graphs
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 2, pp. 357-373

Voir la notice de l'article provenant de la source Library of Science

An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ 1,2,...,t there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ , then the Cartesian product of these graphs belongs to . Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if G ∈ , then G[nK₁] ∈ for any n ∈ ℕ. Furthermore, we show that if G,H ∈ and H is a regular graph, then strong and lexicographic products of graphs G,H belong to . We also prove that tensor and strong tensor products of graphs G,H belong to if G ∈ and H is a regular graph.
Keywords: edge coloring, interval coloring, regular graph, products of graphs 
@article{DMGT_2011_31_2_a11,
     author = {Petrosyan, Petros},
     title = {Interval edge colorings of some products of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {357--373},
     publisher = {mathdoc},
     volume = {31},
     number = {2},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a11/}
}
TY  - JOUR
AU  - Petrosyan, Petros
TI  - Interval edge colorings of some products of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 357
EP  - 373
VL  - 31
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a11/
LA  - en
ID  - DMGT_2011_31_2_a11
ER  - 
%0 Journal Article
%A Petrosyan, Petros
%T Interval edge colorings of some products of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 357-373
%V 31
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a11/
%G en
%F DMGT_2011_31_2_a11
Petrosyan, Petros. Interval edge colorings of some products of graphs. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 2, pp. 357-373. http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a11/