EDGE COLORING OF CACTUS GRAPHS WITH GIVEN SPECTRUMS

International Academy Journal Web of Scholar

View Publication Info
 
 
Field Value
 
Title EDGE COLORING OF CACTUS GRAPHS WITH GIVEN SPECTRUMS
EDGE COLORING OF CACTUS GRAPHS WITH GIVEN SPECTRUMS
 
Creator Albert Khachik Sahakyan
 
Subject cactus graphs, block-cut tree, edge coloring, restrictions on spectrums, dynamic programming
cactus graphs, block-cut tree, edge coloring, restrictions on spectrums, dynamic programming
 
Description An edge-coloring of a graph G is a coloring of the graph edges with integers such that the colors of the edges incident to any vertex of G are distinct. For an edge coloring α and a vertex v the set of all the colors of the incident edges of v is called the spectrum of that vertex in α and is denoted by Sa(V). We consider the case where the spectrum for each vertex V is provided S(V), and the problem is to find an edge-coloring α such that for every vertex V, Sa(V) = S(V). We provide an O(N2) algorithm that inds such an edge-coloring for cactus graphs that satisfies all the restrictions. If it is impossible to have an edge-coloring hat satisfiesthe restrictions of the spectrums the algorithm will tell that too.
An edge-coloring of a graph G is a coloring of the graph edges with integers such that the colors of the edges incident to any vertex of G are distinct. For an edge coloring α and a vertex v the set of all the colors of the incident edges of v is called the spectrum of that vertex in α and is denoted by Sa(V). We consider the case where the spectrum for each vertex V is provided S(V), and the problem is to find an edge-coloring α such that for every vertex V, Sa(V) = S(V). We provide an O(N2) algorithm that inds such an edge-coloring for cactus graphs that satisfies all the restrictions. If it is impossible to have an edge-coloring hat satisfiesthe restrictions of the spectrums the algorithm will tell that too.
 
Publisher RS Global Sp. z O.O.
 
Date 2021-06-10
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
 
Format application/pdf
 
Identifier https://rsglobal.pl/index.php/wos/article/view/2055
10.31435/rsglobal_wos/30062021/7617
 
Source International Academy Journal Web of Scholar; No 2(52) (2021): International Academy Journal Web of Scholar
International Academy Journal Web of Scholar; № 2(52) (2021): International Academy Journal Web of Scholar
2518-1688
2518-167X
 
Language eng
 
Relation https://rsglobal.pl/index.php/wos/article/view/2055/1813
 
Rights Copyright (c) 2021 The author
https://creativecommons.org/licenses/by/4.0
 

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us

Twitter

Copyright © 2015-2018 Simon Fraser University Library