2021; Physical and Mathematical Sciences, 55(3 (256): 160–168
Shared with The Gufo

INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES

Received: 2025-01-27 · Published: 2021-11-05

Shared article.
Original title
INTERVAL VERTEX-COLORINGS OF CACTUS GRAPHS WITH RESTRICTIONS ON VERTICES
Author
Albert Sahakyan
Published
2021-11-05
Licence
Creative Commons Attribution-NonCommercial 4.0 International
Original
https://doi.org/10.46991/PYSU:A/2021.55.3.160

Abstract

An interval vertex-coloring of a graph G is a coloring of the vertices of the graph with intervals of integers such that the intervals of any two adjacent vertices do not intersect. In this paper we consider the case, where for each vertex v there is a length l(v) and a set of colors S(v), from which the colors should be and it is required to find an interval vertex-coloring γ such that for each vertex v the restrictions are met, i.e. |γ(v)|=l(v),γ(v)⊆S(v). We will provide a pseudo-polynomial algorithm for cactus graphs. If it is impossible to have an interval vertex-coloring that satisfies all the restrictions, then the algorithm will tell that as well.
1 / ? 100% Open in new tab Download Cite

Loading the full text…

Download Follow Updates