<  Back to the Polytechnique Montréal portal

A note on r-equitable k-colorings of trees

Alain Hertz and Bernard Ries

Article (2014)

[img]
Preview
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

Open Access document in PolyPublie
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: 10 Mar 2020 01:20
PolyPublie URL: https://publications.polymtl.ca/3627/
Document issued by the official publisher
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

Repository Staff Only