RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Bul. Acad. Ştiinţe Repub. Mold. Mat.: Year: Volume: Issue: Page: Find

 Bul. Acad. Ştiinţe Repub. Mold. Mat., 2012, Number 1, Pages 50–58 (Mi basm303)

On cyclically-interval edge colorings of trees

R. R. Kamalian

Institute for Informatics and Automation Problems, National Academy of Sciences of RA, Yerevan, Republic of Armenia

Abstract: For an undirected, simple, finite, connected graph $G$, we denote by $V(G)$ and $E(G)$ the sets of its vertices and edges, respectively. A function $\varphi\colon E(G)\to\{1,2,…,t\}$ is called a proper edge $t$-coloring of a graph $G$ if adjacent edges are colored differently and each of $t$ colors is used. An arbitrary nonempty subset of consecutive integers is called an interval. If $\varphi$ is a proper edge $t$-coloring of a graph $G$ and $x\in V(G)$, then $S_G(x,\varphi)$ denotes the set of colors of edges of $G$ which are incident with $x$. A proper edge $t$-coloring $\varphi$ of a graph $G$ is called a cyclically-interval $t$-coloring if for any $x\in V(G)$ at least one of the following two conditions holds: a) $S_G(x,\varphi)$ is an interval, b) $\{1,2,…,t\}\setminus S_G(x,\varphi)$ is an interval. For any $t\in\mathbb N$, let $\mathfrak M_t$ be the set of graphs for which there exists a cyclically-interval $t$-coloring, and let $\mathfrak M\equiv\bigcup_{t\geq1}\mathfrak M_t$. For an arbitrary tree $G$, it is proved that $G\in\mathfrak M$ and all possible values of $t$ are found for which $G\in\mathfrak M_t$.

Keywords and phrases: tree, interval edge coloring, cyclically-interval edge coloring.

Full text: PDF file (137 kB)
References: PDF file   HTML file

Bibliographic databases:
MSC: 05C05, 05C15
Language:

Citation: R. R. Kamalian, “On cyclically-interval edge colorings of trees”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2012, no. 1, 50–58

Citation in format AMSBIB
\Bibitem{Kam12} \by R.~R.~Kamalian \paper On cyclically-interval edge colorings of trees \jour Bul. Acad. \c Stiin\c te Repub. Mold. Mat. \yr 2012 \issue 1 \pages 50--58 \mathnet{http://mi.mathnet.ru/basm303} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2987326} \zmath{https://zbmath.org/?q=an:1252.05066} 

• http://mi.mathnet.ru/eng/basm303
• http://mi.mathnet.ru/eng/basm/y2012/i1/p50

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. R. Kamalian, “On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles”, Open Journal of Discrete Mathematics, 3:1 (2013), 43–48
2. Bodur M., Luedtke J.R., “Integer Programming Formulations For Minimum Deficiency Interval Coloring”, Networks, 72:2 (2018), 249–271
•  Number of views: This page: 137 Full text: 30 References: 29 First page: 1