Open AccessThe set chromatic numbers of the middle graph of graphs
Author(s) -
Gerone Russel J Eugenio,
Mari-Jo P. Ruiz,
Mark Anthony C. Tolentino
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1836/1/012014
Subject(s) - combinatorics , complete coloring , mathematics , brooks' theorem , fractional coloring , list coloring , edge coloring , chromatic scale , graph coloring , vertex (graph theory) , greedy coloring , discrete mathematics , windmill graph , graph , graph power , 1 planar graph , chordal graph , line graph
For a simple connected graph G , let c : V ( G ) → ℕ be a vertex coloring of G, where adjacent vertices may be colored the same. The neighborhood color set of a vertex v , denoted by NC ( v ), is the set of colors of the neighbors of v . The coloring c is called a set coloring provided that NC ( u ) ≠ NC ( v ) for every pair of adjacent vertices u and v of G . The minimum number of colors needed for a set coloring of G is referred to as the set chromatic number of G and is denoted by χ s (G). In this work, the set chromatic number of graphs is studied in relation to the graph operation called middle graph. Our results include the exact set chromatic numbers of the middle graph of cycles, paths, star graphs, double-star graphs, and some trees of height 2. Moreover, we establish the sharpness of some bounds on the set chromatic number of general graphs obtained using this operation. Finally, we develop an algorithm for constructing an optimal set coloring of the middle graph of trees of height 2 under some assumptions.