The Set Chromatic Numbers of the Middle Graph of Tree Families
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...
Saved in:
| Main Authors: | , |
|---|---|
| 格式: | text |
| 出版: |
Archīum Ateneo
2023
|
| 主題: | |
| 在線閱讀: | https://archium.ateneo.edu/mathematics-faculty-pubs/245 https://archium.ateneo.edu/context/mathematics-faculty-pubs/article/1246/viewcontent/R_MathTech22_Tolentino_Eugenio.pdf |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 總結: | 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 |
|---|