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

Discrete and Computational Geometry, Graphs, and Games

Abstract

Suppose $G$ is a simple, undirected, finite, nontrivial, and connected graph and that $c: V(G) \to \mathbb{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) \neq 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 $\chi_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) \cup 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 \in V(G)$, $v \in 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.