Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Interval Edge-Colorings of Cartesian Products of Graphs I

100%

Petrosyan P. A., Khachatrian H. H., Tananyan H. G.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 3

613-632

A proper 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 form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. Let [...] be the set of all interval colorable graphs. For a 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), respectively. In this paper we first show that if G is an r-regular graph and G ∈ [...] , then W(G⃞Pm) ≥ W(G) + W(Pm) + (m − 1)r (m ∈ N) and W(G⃞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⃞H is planar and both factors have at least 3 vertices, then G⃞H [...] N and w(G⃞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 ≤ [...]

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Khachatrian H. H.

1 Petrosyan P. A.

1 Tananyan H. G.

1 2013

Wyniki wyszukiwania

Interval Edge-Colorings of Cartesian Products of Graphs I