A Note on Distance-Fall Colorings

Articles in Press

Document Type : Special issue of CCO to honor Odile Favaron

Authors

1 School of Mathematical and Statistical Sciences Clemson University, USA

2 Soka University of America, USA

3 University of Johannesburg, South Africa

Abstract

We say a proper coloring  of a graph is distance-$k$ fall if every vertex is within distance $k$ of at least one vertex of every color. We show that if $G$ is a connected graph of order at least $3$ that is $3$-colorable, then it has a distance-2 fall 3-coloring. Further, for every integer $k\ge 2$, if $T$ is a tree of order at least $k$, then $T$ has a $k$-coloring such that every vertex is within distance $k-1$ of every color. This proves an old conjecture of Beineke and Henning that every tree of order $n$ has an independent distance-$d$-dominating set of size at most $n/(d + 1)$.

Keywords

Main Subjects

References

[1] L.W. Beineke and M.A. Henning, Some extremal results on independent distance domination in graphs, Ars Combin. 37 (1994), 223–233.
2] R. Boutrig, M. Chellali, T.W. Haynes, and S.T. Hedetniemi, Vertex-edge domination in graphs, Aequ. Math. 90 (2016), no. 2, 355–366. https://doi.org/10.1007/s00010-015-0354-2
[3] G. Boyer and W. Goddard, Bounds on independent isolation in graphs, Discrete Appl. Math. 372 (2025), 143–149.
https://doi.org/10.1016/j.dam.2025.04.016
[4] C. Bujtás, V.I. Chenoweth, S. Klavžar, and G. Zhang, Revisiting $d$-distance (independent) domination in trees and in bipartite graphs, arXiv preprint arXiv:2508.12804 (2025).
[5] J.E. Dunbar, S.M. Hedetniemi, S.T. Hedetniemi, D.P. Jacobs, J. Knisely, R.C. Laskar, and D.F. Rall, Fall colorings of graphs, J. Combin. Math. Combin. Comput. 33 (2000), 257–273.
[6] O. Favaron and P. Kaemawichanurat, Inequalities between the $K_k$-isolation number and the independent $K_k$-isolation number of a graph, Discrete Appl. Math. 289 (2021), 93–97. https://doi.org/10.1016/j.dam.2020.09.011
[7] H. Kaul and C. Mitillos, On graph fall-coloring-operators and heredity, J. Combin. Math. Combin. Comput. 106 (2018), 125–151.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 06 January 2026

Files

Share

How to cite

Statistics