TY - JOUR
AU - Tolentino, Mark Anthony C.
AU - Eugenio, Gerone Russel J.
PY - 2023/12/31
Y2 - 2024/09/15
TI - On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families: Discrete and Computational Geometry, Graphs, and Games
JF - Thai Journal of Mathematics
JA - Thai J Math
VL - 21
IS - 4
SE - Articles
DO -
UR - https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1549
SP - 835–853
AB - <p>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)
eq 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.</p>
ER -