Mathematics Student Seminar Series: The Set Chromatic Numbers of the Middle and Total Graph of Graphs

Mathematics Student Seminar Series
The Set Chromatic Numbers of the Middle and Total Graph of Graphs

by Gerone Russel J. Eugenio
Central Luzon State University

Date: Friday, 18 March 2022
Time: 4 pm
Venue: bit.ly/AdmuMathSeminar

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 associated with these colorings. First introduced by Chartrand, Okamoto, Rasmussen, and Zhang in 2009, one example of a neighbor-distinguishing coloring is called the set coloring, 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.

Key Words: vertex coloring, set coloring, set chromatic number