On Closed Modular Colorings of Trees
Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex colorin...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1678 |
| _version_ | 1797713228475662336 |
|---|---|
| author | Phinezy Bryan Zhang Ping |
| author_facet | Phinezy Bryan Zhang Ping |
| author_sort | Phinezy Bryan |
| collection | DOAJ |
| description | Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood of v. Then c is called a closed modular k-coloring if c′(u) 6= c′(v) in Zk for all pairs u, v of adjacent vertices that are not true twins. The minimum k for which G has a closed modular k-coloring is the closed modular chromatic number mc(G) of G. The closed modular chromatic number is investigated for trees and determined for several classes of trees. For each tree T in these classes, it is shown that mc(T) = 2 or mc(T) = 3. A closed modular k-coloring c of a tree T is called nowhere-zero if c(x) 6= 0 for each vertex x of T. It is shown that every tree of order 3 or more has a nowhere-zero closed modular 4-coloring. |
| first_indexed | 2024-03-12T07:33:19Z |
| format | Article |
| id | doaj.art-8f7cc77ac66845818ae1775563e4e018 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T07:33:19Z |
| publishDate | 2013-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-8f7cc77ac66845818ae1775563e4e0182023-09-02T21:42:47ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-05-0133241142810.7151/dmgt.1678On Closed Modular Colorings of TreesPhinezy Bryan0Zhang Ping1Department of Mathematics Western Michigan University Kalamazoo, MI 49008, USADepartment of Mathematics Western Michigan University Kalamazoo, MI 49008, USATwo vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood of v. Then c is called a closed modular k-coloring if c′(u) 6= c′(v) in Zk for all pairs u, v of adjacent vertices that are not true twins. The minimum k for which G has a closed modular k-coloring is the closed modular chromatic number mc(G) of G. The closed modular chromatic number is investigated for trees and determined for several classes of trees. For each tree T in these classes, it is shown that mc(T) = 2 or mc(T) = 3. A closed modular k-coloring c of a tree T is called nowhere-zero if c(x) 6= 0 for each vertex x of T. It is shown that every tree of order 3 or more has a nowhere-zero closed modular 4-coloring.https://doi.org/10.7151/dmgt.1678treesclosed modular k-coloringclosed modular chromatic number |
| spellingShingle | Phinezy Bryan Zhang Ping On Closed Modular Colorings of Trees Discussiones Mathematicae Graph Theory trees closed modular k-coloring closed modular chromatic number |
| title | On Closed Modular Colorings of Trees |
| title_full | On Closed Modular Colorings of Trees |
| title_fullStr | On Closed Modular Colorings of Trees |
| title_full_unstemmed | On Closed Modular Colorings of Trees |
| title_short | On Closed Modular Colorings of Trees |
| title_sort | on closed modular colorings of trees |
| topic | trees closed modular k-coloring closed modular chromatic number |
| url | https://doi.org/10.7151/dmgt.1678 |
| work_keys_str_mv | AT phinezybryan onclosedmodularcoloringsoftrees AT zhangping onclosedmodularcoloringsoftrees |