Document Type

Article

Publication Date

1-1-2023

Abstract

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

Download

Included in

Mathematics Commons

Share

COinS