| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
18 February 2025 |
|
| | | |
|
Article overview
| |
|
Interval edge-colorings of composition of graphs | Petros A. Petrosyan
; Hayk H. Tepanyan
; | Date: |
1 Aug 2015 | Abstract: | An edge-coloring of a graph $G$ with consecutive integers
$c_{1},ldots,c_{t}$ is called an emph{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 $mathfrak{N}$. In 2004, Giaro and Kubale showed
that if $G,Hin mathfrak{N}$, then the Cartesian product of these graphs
belongs to $mathfrak{N}$. In the same year they formulated a similar problem
for the composition of graphs as an open problem. Later, in 2009, the first
author showed that if $G,Hin mathfrak{N}$ and $H$ is a regular graph, then
$G[H]in mathfrak{N}$. In this paper, we prove that if $Gin mathfrak{N}$ and
$H$ has an interval coloring of a special type, then $G[H]in mathfrak{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
$Gin mathfrak{N}$ and $T$ is a tree, then $G[T]in mathfrak{N}$. | Source: | arXiv, 1508.0158 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|