The Set Chromatic Numbers of the Middle and Total Graphs of a Graph
In the area of graph colorings, much research has been done on the topic of neighbor- distinguishing colorings and the effects of graph operations on the chromatic numbers as- sociated with these colorings. First introduced by Chartrand, Okamoto, Rasmussen, and Zhang in 2009, one example of a neighb...
Saved in:
Main Author: | |
---|---|
Format: | text |
Published: |
Archīum Ateneo
2020
|
Subjects: | |
Online Access: | https://archium.ateneo.edu/theses-dissertations/531 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Ateneo De Manila University |
id |
ph-ateneo-arc.theses-dissertations-1657 |
---|---|
record_format |
eprints |
spelling |
ph-ateneo-arc.theses-dissertations-16572021-10-06T05:00:04Z The Set Chromatic Numbers of the Middle and Total Graphs of a Graph Eugenio, Gerone Russel In the area of graph colorings, much research has been done on the topic of neighbor- distinguishing colorings and the effects of graph operations on the chromatic numbers as- sociated with these colorings. First introduced by Chartrand, Okamoto, Rasmussen, and Zhang in 2009, one example of a neighbor-distinguishing coloring is called the set color- ing, which is defined as follows: For a simple connected graph G, let c : V (G) → N be a vertex coloring of G, where adjacent vertices may be colored the same. The neighborhood color set of a vertex v of G, denoted by NC(v), is the set of colors of the neighbors of v. The coloring c is called a set coloring provided that NC(u) 6= NC(v) for every pair of adjacent vertices u and v of G. The minimum number of colors needed for a set coloring of G is referred to as the set chromatic number of G and is denoted by χs(G). In the literature, the set chromatic number has been studied with respect to some graph operations such as join, corona, and comb product. In this work, the set chromatic number of graphs is studied in relation to two other well-studied graph operations: middle graph and total graph. Our results include the exact set chromatic number of the middle and total graphs of cycles, paths, star graphs, double star graphs, and trees of height 2. Moreover, we establish the sharpness of some bounds on the set chromatic number of general graphs obtained using these operations. Finally, we develop algorithms for constructing optimal set colorings of the middle and total graphs of trees of height 2 under some assumptions. 2020-01-01T08:00:00Z text https://archium.ateneo.edu/theses-dissertations/531 Theses and Dissertations (All) Archīum Ateneo vertex coloring, set coloring, set chromatic number |
institution |
Ateneo De Manila University |
building |
Ateneo De Manila University Library |
continent |
Asia |
country |
Philippines Philippines |
content_provider |
Ateneo De Manila University Library |
collection |
archium.Ateneo Institutional Repository |
topic |
vertex coloring, set coloring, set chromatic number |
spellingShingle |
vertex coloring, set coloring, set chromatic number Eugenio, Gerone Russel The Set Chromatic Numbers of the Middle and Total Graphs of a Graph |
description |
In the area of graph colorings, much research has been done on the topic of neighbor- distinguishing colorings and the effects of graph operations on the chromatic numbers as- sociated with these colorings. First introduced by Chartrand, Okamoto, Rasmussen, and Zhang in 2009, one example of a neighbor-distinguishing coloring is called the set color- ing, which is defined as follows: For a simple connected graph G, let c : V (G) → N be a vertex coloring of G, where adjacent vertices may be colored the same. The neighborhood color set of a vertex v of G, denoted by NC(v), is the set of colors of the neighbors of v. The coloring c is called a set coloring provided that NC(u) 6= NC(v) for every pair of adjacent vertices u and v of G. The minimum number of colors needed for a set coloring of G is referred to as the set chromatic number of G and is denoted by χs(G). In the literature, the set chromatic number has been studied with respect to some graph operations such as join, corona, and comb product. In this work, the set chromatic number of graphs is studied in relation to two other well-studied graph operations: middle graph and total graph. Our results include the exact set chromatic number of the middle and total graphs of cycles, paths, star graphs, double star graphs, and trees of height 2. Moreover, we establish the sharpness of some bounds on the set chromatic number of general graphs obtained using these operations. Finally, we develop algorithms for constructing optimal set colorings of the middle and total graphs of trees of height 2 under some assumptions. |
format |
text |
author |
Eugenio, Gerone Russel |
author_facet |
Eugenio, Gerone Russel |
author_sort |
Eugenio, Gerone Russel |
title |
The Set Chromatic Numbers of the Middle and Total Graphs of a Graph |
title_short |
The Set Chromatic Numbers of the Middle and Total Graphs of a Graph |
title_full |
The Set Chromatic Numbers of the Middle and Total Graphs of a Graph |
title_fullStr |
The Set Chromatic Numbers of the Middle and Total Graphs of a Graph |
title_full_unstemmed |
The Set Chromatic Numbers of the Middle and Total Graphs of a Graph |
title_sort |
set chromatic numbers of the middle and total graphs of a graph |
publisher |
Archīum Ateneo |
publishDate |
2020 |
url |
https://archium.ateneo.edu/theses-dissertations/531 |
_version_ |
1715215770719354880 |