<  Back to the Polytechnique Montréal portal

A note on r-equitable k-colorings of trees

Alain Hertz and Bernard Ries

Article (2014)

Open Acess document in PolyPublie and at official publisher
[img]
Preview
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution Non-commercial Share Alike
Download (101kB)
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

Subjects: 2900 Pure mathematics > 2911 Set theory and general topology
2950 Applied mathematics > 2950 Applied mathematics
Department: Department of Mathematics and Industrial Engineering
Research Center: GERAD - Research Group in Decision Analysis
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
DOI: 10.2298/yjor130704039h
Official URL: https://doi.org/10.2298/yjor130704039h
Date Deposited: 09 Mar 2020 14:23
Last Modified: 30 Apr 2025 15:51
Cite in APA 7: Hertz, A., & Ries, B. (2014). A note on r-equitable k-colorings of trees. Yugoslav Journal of Operations Research, 24(2), 293-298. https://doi.org/10.2298/yjor130704039h

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only

View Item View Item