آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 123 |
| تعداد مقالات | 1,578 |
| تعداد مشاهده مقاله | 1,707,519 |
| تعداد دریافت فایل اصل مقاله | 1,590,793 |
A Note on Distance-Fall Colorings | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 8، دوره 11، شماره 4، اسفند 2026، صفحه 1157-1161 اصل مقاله (286.41 K) | ||
| نوع مقاله: Short notes | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.30962.2683 | ||
| نویسندگان | ||
| Wayne Goddard* 1؛ Sonwabile Mafunda2، 3 | ||
| 1School of Mathematical and Statistical Sciences Clemson University, USA | ||
| 2Soka University of America, USA | ||
| 3University of Johannesburg, South Africa | ||
| چکیده | ||
| 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)$. | ||
| کلیدواژهها | ||
| fall coloring؛ distance-$k$ domination؛ chromatic number | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 204 تعداد دریافت فایل اصل مقاله: 135 |
||