The Set Chromatic Numbers of the Middle and Total Graphs of a Graph

• Main Author: Eugenio, Gerone Russel
• Format: text
• Published: Archīum Ateneo 2020
• Subjects: vertex coloring, set coloring, set chromatic number
• Online Access: https://archium.ateneo.edu/theses-dissertations/531
• Institution: Ateneo De Manila University

In the area of graph colorings, much research has been done on the topic of neighbor- distinguishing colorings and the effects of graph operations on the chromatic numbers as- sociated with these colorings. First introduced by Chartrand, Okamoto, Rasmussen, and Zhang in 2009, one example of a neighbor-distinguishing coloring is called the set color- ing, which is defined as follows: 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 of G, 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) 6= 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 the literature, the set chromatic number has been studied with respect to some graph operations such as join, corona, and comb product. In this work, the set chromatic number of graphs is studied in relation to two other well-studied graph operations: middle graph and total graph. Our results include the exact set chromatic number of the middle and total graphs of cycles, paths, star graphs, double star graphs, and trees of height 2. Moreover, we establish the sharpness of some bounds on the set chromatic number of general graphs obtained using these operations. Finally, we develop algorithms for constructing optimal set colorings of the middle and total graphs of trees of height 2 under some assumptions.