Alain Hertz and Bernard Ries
Article (2014)
|
Published Version Terms of Use: Creative Commons Attribution Non-commercial Share Alike . Download (163kB) |
Cite this document: | Hertz, A. & Ries, B. (2014). A note on r-equitable k-colorings of trees. Yugoslav Journal of Operations Research, 24(2), p. 293-298. doi:10.2298/yjor130704039h |
---|
Show abstract
Hide abstract
Abstract
A graph G = (V, E) is r-equitably k-colorable if there exists a partition of V into k independent sets V¹, V², ... , Vk such that | |Vi| − |Vj| | ≤ r for all i, j ∈ {1, 2, ... , k}. In this note, we show that if two trees T¹ and T² of order at least two are r-equitably k-colorable for r ≥ 1 and k ≥ 3, then all trees obtained by adding an arbitrary edge between T¹ and T² are also r-equitably k-colorable.
Uncontrolled Keywords
Trees, equitable coloring, independent sets
![]() |
|
Subjects: |
2900 Mathématiques pures > 2911 Théorie des ensembles et topologie générale 2950 Mathématiques appliquées > 2950 Mathématiques appliquées |
---|---|
Department: | Département de mathématiques et de génie industriel |
Research Center: | GERAD - Groupe d'études et de recherche en analyse des décisions |
Date Deposited: | 09 Mar 2020 14:23 |
Last Modified: | 08 Apr 2021 10:43 |
PolyPublie URL: | https://publications.polymtl.ca/3627/ |
![]() |
|
Journal Title: | Yugoslav Journal of Operations Research (vol. 24, no. 2) |
---|---|
Publisher: | Faculty of Organizational Sciences, Belgrade, Mihajlo Pupin Institute, Belgrade, Faculty of Transport and Traffic Engineering, Belgrade, Faculty of Mining and Geology – Department of Mining, Belgrade, Mathematical Institute SANU, Belgrade |
Official URL: | https://doi.org/10.2298/yjor130704039h |
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads
Dimensions