TY - GEN

T1 - The Graceful Chromatic Number for Some Particular Classes of Graphs

AU - Mincu, Radu

AU - Obreja, Camelia

AU - Popa, Alexandru

PY - 2019/9

Y1 - 2019/9

N2 - Graph colorings are a major area of study in graph theory involving the constrained assignment of labels (colors) to vertices or edges. There are many types of colorings defined in the literature. The most common type of coloring is the proper vertex k-coloring which is defined as a vertex coloring from a set of k colors such that no two adjacent vertices share a common color. Our central focus in this paper is a variant of the proper vertex k-coloring problem, termed graceful coloring introduced by Gary Chartrand in 2015. A graceful k-coloring of an undirected connected graph G is a proper vertex coloring using k colors that induces a proper edge coloring, where the color for an edge (u,v) is the absolute value of the difference between the colors assigned to vertices u and v. In this work we find the graceful chromatic number, the minimum k for which a graph has a graceful k-coloring, for some well-known graphs and classes of graphs, such as diamond graph, Petersen graph, Moser spindle graph, Goldner-Harary graph, friendship graphs, fan graphs and others.

AB - Graph colorings are a major area of study in graph theory involving the constrained assignment of labels (colors) to vertices or edges. There are many types of colorings defined in the literature. The most common type of coloring is the proper vertex k-coloring which is defined as a vertex coloring from a set of k colors such that no two adjacent vertices share a common color. Our central focus in this paper is a variant of the proper vertex k-coloring problem, termed graceful coloring introduced by Gary Chartrand in 2015. A graceful k-coloring of an undirected connected graph G is a proper vertex coloring using k colors that induces a proper edge coloring, where the color for an edge (u,v) is the absolute value of the difference between the colors assigned to vertices u and v. In this work we find the graceful chromatic number, the minimum k for which a graph has a graceful k-coloring, for some well-known graphs and classes of graphs, such as diamond graph, Petersen graph, Moser spindle graph, Goldner-Harary graph, friendship graphs, fan graphs and others.

KW - graceful chromatic number

KW - graceful coloring

KW - undirected graph

KW - vertex coloring

UR - http://www.scopus.com/inward/record.url?scp=85083708772&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85083708772&partnerID=8YFLogxK

U2 - 10.1109/SYNASC49474.2019.00024

DO - 10.1109/SYNASC49474.2019.00024

M3 - Conference contribution

AN - SCOPUS:85083708772

T3 - Proceedings - 21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2019

SP - 109

EP - 115

BT - Proceedings - 21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2019

A2 - Hong, Hoon

A2 - Negru, Viorel

A2 - Petcu, Dana

A2 - Zaharie, Daniela

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2019

Y2 - 4 September 2019 through 7 September 2019

ER -