On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families
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 th...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | text |
| Published: |
Archīum Ateneo
2023
|
| Subjects: | |
| Online Access: | https://archium.ateneo.edu/mathematics-faculty-pubs/246 https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1549/1512 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Ateneo De Manila University |
| Summary: | 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. |
|---|