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∈V−S, the set S∪{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 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 χi(G). A coloring 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 χγ(G). In this paper, we prove that every tree T satisfies χi(T)=ir(T) unless T is a star. Further, we prove that γ(T)≤χγ(T)≤γ(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, M.A. Henning, I.S. Hamid, and P. Kaemawichanurat, On irredundance coloring and irredundance compelling coloring of graphs, Discrete Appl. Math. 369 (2025), 149–161.  https://doi.org/10.1016/j.dam.2025.03.025
Communications in Combinatorics and Optimization

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

Files

Share

How to cite

Statistics