Irredundance chromatic number and gamma chromatic number of trees

Articles in Press

Document Type : Short notes

Authors

1 Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, Thailand

2 Mathematics and Statistics with Application (MaSA)

Abstract

A vertex subset $S$ of a graph $G = (V, E)$ is irredundant if every vertex in $S$ has a private neighbor with respect to $S$. An irredundant set $S$ of $G$ is maximal if, for any $v \in V - S$, the set $S \cup \{v\}$ is no longer irredundant. The lower irredundance number of $G$ is the minimum cardinality of a maximal irredundant set of $G$ and is denoted by $ir(G)$. A coloring $\mathcal{C}$ of $G$ is said to be the irredundance coloring if there exists a maximal irredundant set $R$ of $G$ such that all the vertices of $R$ receive different colors. The minimum number of colors required for an irredundance coloring of $G$ is called the irredundance chromatic number of $G$, and is denoted by $\chi_{i}(G)$. A coloring $\mathcal{C}$ of $G$ is said to be the gamma coloring if there exists a dominating set $D$ of $G$ such that all the vertices of $D$ receive different colors. The minimum number of colors required for a gamma coloring of $G$ is called the gamma chromatic number of $G$, and is denoted by $\chi_{\gamma}(G)$. In this paper, we prove that every tree $T$ satisfies $\chi_{i}(T) = ir(T)$ unless $T$ is a star. Further, we prove that $\gamma(T) \leq \chi_{\gamma}(T) \leq \gamma(T) + 1$. We characterize all trees satisfying the upper bound.

Keywords

Main Subjects

References

[1] L.W. Beineke and R.J. Wilson, Topics in Chromatic Graph Theory, Cambridge University Press, 2015.
[2] G. Chartrand and L. Lesniak, Graphs and Digraphs, sixth edition, Chapman & Hall London, 2016.
[3] R. Gnanaprakasam and I.S. Hamid, Gamma coloring of mycielskian graphs, Indian J. Sci. Technol. 15 (2022), no. 20, 976–982.
https://doi.org/10.17485/IJST/v15i20.2324
[4] T.W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 2013.
[5] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Volume 2: Advanced Topics (1st ed.), Chapman & Hall/CRC Pure and Applied Mathematics, 1998.
[6] D.A. Kalarkop and P. Kaemawichanurat, On irredundance coloring and irredundance compelling coloring of graphs, arXiv preprint arXiv:2311.06161 (2023).
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 12 August 2024

Files

Share

How to cite

Statistics