The Set Chromatic Numbers of the Middle Graph of Tree Families

• Main Authors: Tolentino, Mark Anthony C, Eugenio, Gerone Russel J.
• Format: text
• Published: Archīum Ateneo 2023
• Subjects: middle graph; Set coloring; Mathematics; Physical Sciences and Mathematics
• Online Access: https://archium.ateneo.edu/mathematics-faculty-pubs/245; https://archium.ateneo.edu/context/mathematics-faculty-pubs/article/1246/viewcontent/R_MathTech22_Tolentino_Eugenio.pdf
• Institution: Ateneo De Manila University

The neighborhood color set of each vertex v in a vertex-colored graph G is defined as the collection of the colors of all the neighbors of v. If there are no two adjacent vertices that have equal neighborhood color sets, then the coloring is called a set coloring of G. The set coloring problem on G refers to the problem of determining its set chromatic number, which refers to the fewest colors using which a set coloring of G may be constructed. In this work, we consider the set coloring problem on graphs obtained from applying middle graph, a unary graph operation. The middle graph of G is the graph whose vertex set is the union of V (G) and E(G) and whose edge set is {{u, uv}: u ∈ V (G) and uv ∈ E(G)} ∪ {{uv1, uv2}: uv1, uv2 ∈ E(G) and v1 ≠ v2}. We consider the set coloring problem on the middle graph of different tree families such as brooms, double brooms and caterpillars. We construct set colorings of such graphs using algorithms or explicit formulas. By proving the optimality of these set colorings, we obtain the set chromatic number for these different graph families