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...

Full description

Saved in:
Bibliographic Details
Main Authors: Tolentino, Mark Anthony C, Eugenio, Gerone Russel J
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
id ph-ateneo-arc.mathematics-faculty-pubs-1247
record_format eprints
spelling ph-ateneo-arc.mathematics-faculty-pubs-12472024-04-01T08:04:52Z On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families Tolentino, Mark Anthony C Eugenio, Gerone Russel J 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. 2023-12-01T08:00:00Z text https://archium.ateneo.edu/mathematics-faculty-pubs/246 https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1549/1512 Mathematics Faculty Publications Archīum Ateneo middle graph neighbor-distinguishing coloring set coloring trees Mathematics Physical Sciences and Mathematics
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 middle graph
neighbor-distinguishing coloring
set coloring
trees
Mathematics
Physical Sciences and Mathematics
spellingShingle middle graph
neighbor-distinguishing coloring
set coloring
trees
Mathematics
Physical Sciences and Mathematics
Tolentino, Mark Anthony C
Eugenio, Gerone Russel J
On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families
description 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.
format text
author Tolentino, Mark Anthony C
Eugenio, Gerone Russel J
author_facet Tolentino, Mark Anthony C
Eugenio, Gerone Russel J
author_sort Tolentino, Mark Anthony C
title On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families
title_short On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families
title_full On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families
title_fullStr On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families
title_full_unstemmed On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families
title_sort on the set chromatic number of the middle graph of extended stars and related tree families
publisher Archīum Ateneo
publishDate 2023
url https://archium.ateneo.edu/mathematics-faculty-pubs/246
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1549/1512
_version_ 1795381050177748992