A note on r-equitable k-colorings of trees
BP2-STS
- Hertz, Alain Ecole Polytechnique de Montréal and GERAD Montréal, Canada
- Ries, Bernard ORCID PSL, Université Paris-Dauphine, Paris Cedex, France
- 2013
Published in:
- Yugoslav Journal of Operations Research. - National Library of Serbia. - 2013, vol. 24, no. 2, p. 293-298
English
A graph G = (V;E) is r-equitably k-colorable if there exists a partition of V into k independent sets V1; V2;...; Vk such that |Vi|-|Vj|<= r for all i,j\in \{1,2,...,k\}. In this note, we show that if two trees T1 and T2 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 T1 and T2 are also r-equitably k-colorable.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- CC BY-NC-SA
- Open access status
- gold
- Identifiers
-
- DOI 10.2298/YJOR130704039H
- ISSN 0354-0243
- Persistent URL
- https://folia.unifr.ch/unifr/documents/322638
Statistics
Document views: 24
File downloads:
- equitable.pdf: 82