Geodesic
Interval vertex-colorings of cactus graphs with restrictions on vertices
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 3, pp. 160-168.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\gamma$ such that for each vertex $v$ the restrictions are met, i.e. $|\gamma(v)|=l(v),\gamma(v)\subseteq 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.
Keywords: cactus graphs, trees, interval vertex-coloring, list coloring, dynamic programming
Mots-clés : pseudo-polynomial algorithm. 
@article{UZERU_2021_55_3_a1,
     author = {A. Kh. Sahakyan and R. R. Kamalian},
     title = {Interval vertex-colorings of cactus graphs with restrictions on vertices},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {160--168},
     publisher = {mathdoc},
     volume = {55},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2021_55_3_a1/}
}
TY  - JOUR
AU  - A. Kh. Sahakyan
AU  - R. R. Kamalian
TI  - Interval vertex-colorings of cactus graphs with restrictions on vertices
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2021
SP  - 160
EP  - 168
VL  - 55
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2021_55_3_a1/
LA  - en
ID  - UZERU_2021_55_3_a1
ER  - 
%0 Journal Article
%A A. Kh. Sahakyan
%A R. R. Kamalian
%T Interval vertex-colorings of cactus graphs with restrictions on vertices
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2021
%P 160-168
%V 55
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2021_55_3_a1/
%G en
%F UZERU_2021_55_3_a1
A. Kh. Sahakyan; R. R. Kamalian. Interval vertex-colorings of cactus graphs with restrictions on vertices. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 3, pp. 160-168. http://geodesic.mathdoc.fr/item/UZERU_2021_55_3_a1/

[1] D. B. West, Introduction to Graph Theory, Prentice-Hall, New Delhi, 1996 | MR | Zbl

[2] T. H. Cormen, et al., Introduction to Algorithms, MIT Press, Cambridge–London, 2009, 253–286 | MR

[3] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Co., San Francisco, 1979, 109–120 | MR

[4] M. Kubale, “Interval Vertex-coloring of a Graph with Forbidden Colors”, Discret. Math., 74 (1989), 125–136 | DOI | MR | Zbl

[5] R. Karp, “Reducibility among Combinatorial Problems”, Complexity Comput. Computs., eds. R. Miller, J. Thatcher, Plenum Press, New York, 1972, 85–103 | DOI | MR | Zbl

[6] S. A. Cook, “The complexity of Theorem Proving Procedures”, Proc. 3d Annual ACM Symposium on Theory of Computing, N.Y., USA, 1971, 151–158 | DOI | Zbl

[7] S. Even, A. Itai, A. Shamir, “On the Complexity of Timetable and Multicommodity Flow Problems”, SIAM J. Comput., 5:4 (1976), 691–703 | DOI | MR | Zbl

[8] M. Kubale, “Interval Edge Coloring of a Graph with Forbidden Colors”, Discret. Math, 121 (1993), 135–143 | DOI | MR | Zbl

[9] P. Erdős, A. L. Rubin, H. Taylor, “Choosability in Graphs”, Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congress. Numer., 26, 1980, 125–157 | MR | Zbl

[10] V. G. Vizing, “Vertex Colorings with Given Colors”, Metody Diskret. Analiz., 29 (1976), 3–10 | MR | Zbl

[11] A. K. Sahakyan, “List Coloring of Block Graphs and Complete Bipartite Graphs”, World Science, 8:69 (2021), 36–43 | DOI

[12] A. K. Sahakyan, R. R. Kamalian, “Interval Edge-Colorings of Trees with Restrictions on the Edges”, Proceedings of the YSU, Physical and Mathematical Sciences, 55:2 (2021), 113–122 | DOI | Zbl

[13] A. K. Sahakyan, “Interval Edge-Coloring with Restrictions on Edges for Graphs with Special Structures of Cycles”, Norwegian Journal of Development of the International Science, 71 (2021), 13–19 | DOI

[14] A. K. Sahakyan, “Interval Edge Coloring of Trees with Strict Restrictions on the Spectrums”, Science Review, 3:38 (2021), 27–29 | DOI

[15] A. K. Sahakyan, “Edge Coloring of Cactus Graphs with Given Spectrums”, International Academy Journal Web of Scholar, 2:52 (2021), 25–28 | DOI