BZPEER

preprint2020arXiv

Improper interval edge colorings of graphs

A $k$ -improper edge coloring of a graph $G$ is a mapping $α:E(G)\longrightarrow \mathbb{N}$ such that at most $k$ edges of $G$ with a common endpoint have the same color. An improper edge coloring of a graph $G$ is called an improper interval edge coloring if the colors of the edges incident to each vertex of $G$ form an integral interval. In this paper we introduce and investigate a new notion, the interval coloring impropriety (or just impropriety) of a graph $G$ defined as the smallest $k$ such that $G$ has a $k$ -improper interval edge coloring; we denote the smallest such $k$ by $μ_{\mathrm{int}}(G)$ . We prove upper bounds on $μ_{\mathrm{int}}(G)$ for general graphs $G$ and for particular families such as bipartite, complete multipartite and outerplanar graphs; we also determine $μ_{\mathrm{int}}(G)$ exactly for $G$ belonging to some particular classes of graphs. Furthermore, we provide several families of graphs with large impropriety; in particular, we prove that for each positive integer $k$ , there exists a graph $G$ with $μ_{\mathrm{int}}(G) =k$ . Finally, for graphs with at least two vertices we prove a new upper bound on the number of colors used in an improper interval edge coloring.

preprint2016arXiv

Interval edge-colorings of complete graphs

An edge-coloring of a graph $G$ with colors $1,2,\ldots,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$ , $W(G)$ denotes the greatest value of $t$ for which $G$ has an interval $t$ -coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of $W(K_{2n})$ is known only for $n \leq 4$ . The second author showed that if $n = p2^q$ , where $p$ is odd and $q$ is nonnegative, then $W(K_{2n}) \geq 4n-2-p-q$ . Later, he conjectured that if $n \in \mathbb{N}$ , then $W(K_{2n}) = 4n - 2 - \left\lfloor\log_2{n}\right\rfloor - \left \| n_2 \right \|$ , where $\left \| n_2 \right \|$ is the number of $1$ 's in the binary representation of $n$ . In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on $W(K_{2n})$ and determine its exact values for $n \leq 12$ .

preprint2016arXiv

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An \emph{interval $t$ -coloring} of a multigraph $G$ is a proper edge coloring with colors $1,\dots,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors. A \emph{cyclic interval $t$ -coloring} of a multigraph $G$ is a proper edge coloring with colors $1,\dots,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$ . Denote by $w(G)$ ( $w_{c}(G)$ ) and $W(G)$ ( $W_{c}(G)$ ) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$ , respectively. We present some new sharp bounds on $w(G)$ and $W(G)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$ -connected multigraph with an interval coloring, then $W(G)\leq 1+\left\lfloor \frac{|V(G)|}{2}\right\rfloor(Δ(G)-1)$ . We also give several results towards the general conjecture that $W_{c}(G)\leq |V(G)|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$ .

preprint2015arXiv

Graph Theory

This book is based on Graph Theory courses taught by P.A. Petrosyan, V.V. Mkrtchyan and R.R. Kamalian at Yerevan State University.

preprint2015arXiv

Interval edge-colorings of composition of graphs

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,H\in \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,H\in \mathfrak{N}$ and $H$ is a regular graph, then $G[H]\in \mathfrak{N}$ . In this paper, we prove that if $G\in \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 $G\in \mathfrak{N}$ and $T$ is a tree, then $G[T]\in \mathfrak{N}$ .

preprint2014arXiv

Interval cyclic edge-colorings of graphs

A proper edge-coloring of a graph $G$ with colors $1,\ldots,t$ is called an \emph{interval cyclic $t$ -coloring} if all colors are used, and the edges incident to each vertex $v\in V(G)$ are colored by $d_{G}(v)$ consecutive colors modulo $t$ , where $d_{G}(v)$ is the degree of a vertex $v$ in $G$ . A graph $G$ is \emph{interval cyclically colorable} if it has an interval cyclic $t$ -coloring for some positive integer $t$ . The set of all interval cyclically colorable graphs is denoted by $\mathfrak{N}_{c}$ . For a graph $G\in \mathfrak{N}_{c}$ , the least and the greatest values of $t$ for which it has an interval cyclic $t$ -coloring are denoted by $w_{c}(G)$ and $W_{c}(G)$ , respectively. In this paper we investigate some properties of interval cyclic colorings. In particular, we prove that if $G$ is a triangle-free graph with at least two vertices and $G\in \mathfrak{N}_{c}$ , then $W_{c}(G)\leq \vert V(G)\vert +Δ(G)-2$ . We also obtain bounds on $w_{c}(G)$ and $W_{c}(G)$ for various classes of graphs. Finally, we give some methods for constructing of interval cyclically non-colorable graphs.

preprint2014arXiv

Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

A total coloring of a graph $G$ is a coloring of its vertices and edges such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. An interval total $t$ -coloring of a graph $G$ is a total coloring of $G$ with colors $1,\ldots,t$ such that all colors are used, and the edges incident to each vertex $v$ together with $v$ are colored by $d_{G}(v)+1$ consecutive colors, where $d_{G}(v)$ is the degree of a vertex $v$ in $G$ . In this paper we prove that all complete multipartite graphs with the same number of vertices in each part are interval total colorable. Moreover, we also give some bounds for the minimum and the maximum span in interval total colorings of these graphs. Next, we investigate interval total colorings of hypercubes $Q_{n}$ . In particular, we prove that $Q_{n}$ ( $n\geq 3$ ) has an interval total $t$ -coloring if and only if $n+1\leq t\leq \frac{(n+1)(n+2)}{2}$ .

preprint2014arXiv

Sequential edge-coloring on the subset of vertices of almost regular graphs

Let $G$ be a graph and $R\subseteq V(G)$ . A proper edge-coloring of a graph $G$ with colors $1,\ldots,t$ is called an $R$ -sequential $t$ -coloring if the edges incident to each vertex $v\in R$ are colored by the colors $1,\ldots,d_{G}(v)$ , where $d_{G}(v)$ is the degree of the vertex $v$ in $G$ . In this note, we show that if $G$ is a graph with $Δ(G)-δ(G)\leq 1$ and $χ^{\prime}(G)=Δ(G)=r$ ( $r\geq 3$ ), then $G$ has an $R$ -sequential $r$ -coloring with $\vert R\vert \geq \left\lceil\frac{(r-1)n_{r}+n}{r}\right\rceil$ , where $n=\vert V(G)\vert$ and $n_{r}=\vert\{v\in V(G):d_{G}(v)=r\}\vert$ . As a corollary, we obtain the following result: if $G$ is a graph with $Δ(G)-δ(G)\leq 1$ and $χ^{\prime}(G)=Δ(G)=r$ ( $r\geq 3$ ), then $Σ^{\prime}(G)\leq \left\lfloor\frac {2n_{r}(2r-1)+n(r-1)(r^{2}+2r-2)}{4r}\right\rfloor$ , where $Σ^{\prime}(G)$ is the edge-chromatic sum of $G$ .

preprint2013arXiv

Interval non-edge-colorable bipartite graphs and multigraphs

An edge-coloring of a graph $G$ with colors $1,...,t$ 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. In 1991 Erdős constructed a bipartite graph with 27 vertices and maximum degree 13 which has no interval coloring. Erdős's counterexample is the smallest (in a sense of maximum degree) known bipartite graph which is not interval colorable. On the other hand, in 1992 Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this paper we give some methods for constructing of interval non-edge-colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs which have no interval coloring, contain 20,19,21 vertices and have maximum degree 11,12,13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.

preprint2013arXiv

On interval edge-colorings of outerplanar graphs

An edge-coloring of a graph $G$ with colors $1,\ldots,t$ 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$ . For an interval colorable graph $G$ , the least value of $t$ for which $G$ has an interval $t$ -coloring is denoted by $w(G)$ . A graph $G$ is outerplanar if it can be embedded in the plane so that all its vertices lie on the same (unbounded) face. In this paper we show that if $G$ is a 2-connected outerplanar graph with $Δ(G)=3$ , then $G$ is interval colorable and \begin{center} $w(G)=\left\{\begin{tabular}{ll} 3, & if $| V(G)|$ is even, \ 4, & if $| V(G)|$ is odd. \end{tabular}% \right.$ \end{center} We also give a negative answer to the question of Axenovich on the outerplanar triangulations.

preprint2013arXiv

On Interval Non-Edge-Colorable Eulerian Multigraphs

An edge-coloring of a multigraph $G$ with colors $1,\ldots,t$ 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. In this note, we show that all Eulerian multigraphs with an odd number of edges have no interval coloring. We also give some methods for constructing of interval non-edge-colorable Eulerian multigraphs.

preprint2012arXiv

Interval colorings of complete balanced multipartite graphs

A graph $G$ is called a complete $k$ -partite ( $k\geq 2$ ) graph if its vertices can be partitioned into $k$ independent sets $V_{1},...,V_{k}$ such that each vertex in $V_{i}$ is adjacent to all the other vertices in $V_{j}$ for $1\leq i<j\leq k$ . A complete $k$ -partite graph $G$ is a complete balanced $k$ -partite graph if $|V_{1}| = |V_{2}| =... = |V_{k}|$ . 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 $G$ has an interval $t$ -coloring for some positive integer $t$ . In this paper we show that a complete balanced $k$ -partite graph $G$ with $n$ vertices in each part is interval colorable if and only if $nk$ is even. We also prove that if $nk$ is even and $(k-1)n\leq t\leq ((3/2)k-1)n-1$ , then a complete balanced $k$ -partite graph $G$ admits an interval $t$ -coloring. Moreover, if $k=p2^{q}$ , where $p$ is odd and $q\in \mathbb{N}$ , then a complete balanced $k$ -partite graph $G$ has an interval $t$ -coloring for each positive integer $t$ satisfying $(k-1)n\leq t\leq (2k-p-q)n-1$ .

preprint2012arXiv

Interval edge-colorings of Cartesian products of graphs I

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 $G$ has an interval $t$ -coloring for some positive integer $t$ . Let $\mathfrak{N}$ be the set of all interval colorable graphs. For a graph $G\in \mathfrak{N}$ , 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\in \mathfrak{N}$ , then $W(G\square P_{m})\geq W(G)+W(P_{m})+(m-1)r$ ( $m\in \mathbb{N}$ ) and $W(G\square C_{2n})\geq W(G)+W(C_{2n})+nr$ ( $n\geq 2$ ). Next, we investigate interval edge-colorings of grids, cylinders and tori. In particular, we prove that if $G\square H$ is planar and both factors have at least 3 vertices, then $G\square H\in \mathfrak{N}$ and $w(G\square H)\leq 6$ . Finally, we confirm the first author's conjecture on the $n$ -dimensional cube $Q_{n}$ and show that $Q_{n}$ has an interval $t$ -coloring if and only if $n\leq t\leq \frac{n(n+1)}{2}$ .

preprint2012arXiv

Interval edge-colorings of graph products

An interval t-coloring of a graph G is a proper edge-coloring of G with colors 1,2,...,t such that at least one edge of G is colored by i, i=1,2,...,t, and the edges incident to each vertex v\in V(G) are colored by d_{G}(v) consecutive colors, where d_{G}(v) is the degree of the vertex v in G. In this paper interval edge-colorings of various graph products are investigated.

preprint2012arXiv

On maximum matchings in almost regular graphs

In 2010, Mkrtchyan, Petrosyan and Vardanyan proved that every graph $G$ with $2\leq δ(G)\leq Δ(G)\leq 3$ contains a maximum matching whose unsaturated vertices do not have a common neighbor, where $Δ(G)$ and $δ(G)$ denote the maximum and minimum degrees of vertices in $G$ , respectively. In the same paper they suggested the following conjecture: every graph $G$ with $Δ(G)-δ(G)\leq 1$ contains a maximum matching whose unsaturated vertices do not have a common neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample $G$ with $Δ(G)=5$ and $δ(G)=4$ . In this note we show that the conjecture is false for graphs $G$ with $Δ(G)-δ(G)=1$ and $Δ(G)\geq 4$ , and for $r$ -regular graphs when $r\geq 7$ .

preprint2011arXiv

A note on triangle-free graphs

We show that if $G$ is a simple triangle-free graph with $n\geq 3$ vertices, without a perfect matching, and having a minimum degree at least $\frac{n-1}{2}$ , then $G$ is isomorphic either to $C_5$ or to $K_{\frac{n-1}{2},\frac{n+1}{2}}$ .

preprint2011arXiv

Interval edge-colorings of cubic graphs

An edge-coloring of a multigraph G with colors 1,2,...,t 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. In this paper we prove that if G is a connected cubic multigraph (a connected cubic graph) that admits an interval t-coloring, then t\leq |V(G)| +1 (t\leq |V(G)|), where V(G) is the set of vertices of G. Moreover, if G is a connected cubic graph, G\neq K_{4}, and G has an interval t-coloring, then t\leq |V(G)| -1. We also show that these upper bounds are sharp. Finally, we prove that if G is a bipartite subcubic multigraph, then G has an interval edge-coloring with no more than four colors.

preprint2010arXiv

Interval edge colorings of some products of graphs

An edge coloring of a graph $G$ with colors $1,2,\ldots ,t$ is called an interval $t$ -coloring if for each $i\in \{1,2,\ldots,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\geq 1$ for which $G$ has an interval $t$ -coloring. Let $\mathfrak{N}$ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if $G,H\in \mathfrak{N}$ , then the Cartesian product of these graphs belongs to $\mathfrak{N}$ . Also, they formulated a similar problem for the lexicographic product as an open problem. In this paper we first show that if $G\in \mathfrak{N}$ , then $G[nK_{1}]\in \mathfrak{N}$ for any $n\in \mathbf{N}$ . Furthermore, we show that if $G,H\in \mathfrak{N}$ and $H$ is a regular graph, then strong and lexicographic products of graphs $G,H$ belong to $\mathfrak{N}$ . We also prove that tensor and strong tensor products of graphs $G,H$ belong to $\mathfrak{N}$ if $G\in \mathfrak{N}$ and $H$ is a regular graph.

preprint2007arXiv

Interval Edge Colourings of Complete Graphs and n-cubes

For complete graphs and n-cubes bounds are found for the possible number of colours in an interval edge colourings.

preprint2007arXiv

On Interval Colorings of Complete k-partite Graphs K_{n}^{k}

Problems of existence, construction and estimation of parameters of interval colorings of complete k-partite graphs K_{n}^{k} are investigated.

Petros A. Petrosyan

Research overview

Is this your work?

20 publications

Improper interval edge colorings of graphs

Interval edge-colorings of complete graphs

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

Graph Theory

Interval edge-colorings of composition of graphs

Interval cyclic edge-colorings of graphs

Interval Total Colorings of Complete Multipartite Graphs and Hypercubes

Sequential edge-coloring on the subset of vertices of almost regular graphs

Interval non-edge-colorable bipartite graphs and multigraphs

On interval edge-colorings of outerplanar graphs

On Interval Non-Edge-Colorable Eulerian Multigraphs

Interval colorings of complete balanced multipartite graphs

Interval edge-colorings of Cartesian products of graphs I

Interval edge-colorings of graph products

On maximum matchings in almost regular graphs

A note on triangle-free graphs

Interval edge-colorings of cubic graphs

Interval edge colorings of some products of graphs

Interval Edge Colourings of Complete Graphs and n-cubes

On Interval Colorings of Complete k-partite Graphs K_{n}^{k}

See the researcher in context

Building this map preview