The Set Chromatic Numbers of the Middle Graph of Graphs

• Main Authors: Eugenio, Gerone Russel J, Ruiz, Mari-Jo P, Tolentino, Mark Anthony C
• Format: text
• Published: Archīum Ateneo 2021
• Subjects: set coloring; middle graph; Mathematics
• Online Access: https://archium.ateneo.edu/mathematics-faculty-pubs/160; https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1165&context=mathematics-faculty-pubs
• Institution: Ateneo De Manila University

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.