The Graceful Chromatic Number for Some Particular Classes of Graphs

Radu Mincu, Camelia Obreja, Alexandru Popa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publicationProceedings - 21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2019
EditorsHoon Hong, Viorel Negru, Dana Petcu, Daniela Zaharie
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages109-115
Number of pages7
ISBN (Electronic)9781728157245
DOIs
Publication statusPublished - Sep 2019
Event21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2019 - Timisoara, Romania
Duration: Sep 4 2019Sep 7 2019

Publication series

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

Conference

Conference21st International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2019
CountryRomania
CityTimisoara
Period9/4/199/7/19

Keywords

  • graceful chromatic number
  • graceful coloring
  • undirected graph
  • vertex coloring

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Science Applications
  • Computational Mathematics
  • Modelling and Simulation

Fingerprint Dive into the research topics of 'The Graceful Chromatic Number for Some Particular Classes of Graphs'. Together they form a unique fingerprint.

Cite this