Document Type
Conference Proceeding
Publication Date
3-23-2021
Abstract
For a simple connected graph G; let c : V (G) → N 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) neq 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 inrelation 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 constructingan optimal set coloring of the middle graph of trees of height 2 under some assumptions.
Recommended Citation
Eugenio, Gerone Russel J.; Ruiz, Mari-Jo P.; and Tolentino, Mark Anthony C., (2021). The Set Chromatic Numbers of the Middle Graph of Graphs. Archīum.ATENEO.
https://archium.ateneo.edu/mathematics-faculty-pubs/160