On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families

Document Type

Article

Publication Date

12-1-2023

Abstract

Suppose G is a simple, undirected, finite, nontrivial, and connected graph and that c: V (G) → N is a vertex coloring, not necessarily proper, of G. As introduced by Chartrand et al., c is called a set coloring of G if NC(u) ≠ NC(v) for every pair of adjacent vertices u and v; here, NC(x) denotes the set of colors of all the neighbors of the vertex x. Moreover, the set chromatic number of G, denoted by χs(G), is the minimum number of colors that can be used to construct a set coloring of G. On the other hand, the middle graph M(G) of a graph G is defined as the graph whose vertex set is V (G) ∪ E(G) and in which two vertices u and v are adjacent if and only if u and v are adjacent edges in G; or u ∈ V (G), v ∈ E(G), and u is incident to v in G. In this paper, we study set colorings in relation to the middle graph of some tree families. We establish lower bounds for the set chromatic number of these graphs and we algorithmically construct set colorings for them. For most cases, we find that the set chromatic number for these graphs is given by min-max formulas.

Link to Full Text

Share

COinS