DEFICIENCY OF OUTERPLANAR GRAPHS

Authors

  • H.H. Khachatryan Chair of Discrete Mathematics and Theoretical Informatics, YSU, Armenia

DOI:

https://doi.org/10.46991/PYSU:A/2017.51.1.022

Keywords:

graph theory, interval edge-coloring, deficiency, outerplanar graph

Abstract

An edge-coloring of a graph G with colors $1,2,...,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$.

Downloads

Published

2017-03-20

How to Cite

Khachatryan, H. (2017). DEFICIENCY OF OUTERPLANAR GRAPHS. Proceedings of the YSU A: Physical and Mathematical Sciences, 51(1 (242), 22–28. https://doi.org/10.46991/PYSU:A/2017.51.1.022

Issue

Section

Mathematics