|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2017, Volume 51, Issue 1, Pages 22–28
(Mi uzeru326)
|
|
|
|
This article is cited in 3 scientific papers (total in 3 papers)
Mathematics
Deficiency of outerplanar graphs
H. H. Khachatrian Chair of Discrete Mathematics and Theoretical Informatics YSU, Armenia
Abstract:
An edge-coloring of a graph $G$ with colors $1, 2, \dots, 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$. $def(G)$ denotes the minimum number of pendant edges that should be attached to $G$ to make it interval colorable. In this paper we study interval colorings of outerplanar graphs. In particular, we show that if $G$ is an outerplanar graph, then $def(G) \leq (|V(G)|-2)/(og(G)-2)$, where $og(G)$ is the length of the shortest cycle with odd number of edges in $G$.
Keywords:
graph theory, interval edge-coloring, deficiency, outerplanar graph.
Received: 18.11.2016 Accepted: 30.11.2016
Citation:
H. H. Khachatrian, “Deficiency of outerplanar graphs”, Proceedings of the YSU, Physical and Mathematical Sciences, 51:1 (2017), 22–28
Linking options:
https://www.mathnet.ru/eng/uzeru326 https://www.mathnet.ru/eng/uzeru/v51/i1/p22
|
|