Համահեղինակ(ներ):

Petrosyan Petros

Ամփոփում:

An edge-coloring of a graph G with consecutive integers c1,…,ct is called an interval t-coloring if all colors are used, 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 it has an interval t-coloring for some positive integer t. The set of all interval colorable graphs is denoted by N. In 2004, Giaro and Kubale showed that if G,H∈N, then the Cartesian product of these graphs belongs to N. In the same year they formulated a similar problem for the composition of graphs as an open problem. Later, in 2009, the second author showed that if G,H∈N and H is a regular graph, then G[H]∈N. In this paper, we prove that if G∈N and H has an interval coloring of a special type, then G[H]∈N. Moreover, we show that all regular graphs, complete bipartite graphs and trees have such a special interval coloring. In particular, this implies that if G∈N and T is a tree, then G[T]∈N.

Հանձնման ամսաթիվը:

01.08.2015

Ընդունման ամսաթիվը:

09.09.2016

Հրատարակման ամսաթիվ:

30.01.2017

Նույնականացուցիչ:

oai:noad.sci.am:136126

DOI:

10.1016/j.dam.2016.09.022

ISSN:

0166-218X

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Discrete Applied Mathematics

Հատոր:

217

Համար:

2

URL:

լրացուցիչ տեղեկատվություն:

tehayk@stanford.edu ; pet_petros@ipia.sci.am

Կազմակերպության անվանում:

Stanford University ; Institute for Informatics and Automation Problems

Երկիր:

Armenia ; US

Ինդեքսավորում:

WOS