A note on r-equitable k-colorings of trees
DOI:
https://doi.org/10.2298/YJOR130704039HKeywords:
trees, equitable coloring, independent setsAbstract
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 {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.References
Private communication, (2012).
Chang, G. J., A note on equitable colorings of forests, European Journal of Combinatorics 30 (2009) 809-812.
Chen, B.-L., Lih, K.-W., Equitable coloring of trees, Journal of Combinatorial Theory Series B 61 (1994) 83-87.
Kierstead, H.A., Kostochka, A.V., Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture, Combinatorica 30(2) (2010) 201-216.
Kierstead, H.A., Kostochka, A.V., Mydlarz, M., Szemeredi, E., A fast algorithm for equitable coloring, Combinatorica 30(2) (2010) 217-224.
Kostochka, A.V., Nakprasit, K., Pemmaraju, S.V., On equitable coloring of d-degenerate graphs, SIAM J. Discrete Math. 19(1) (2005) 83-95.
Luo, R., Sereni, J.-S., Stephens, D. C., Xu, G., Equitable coloring of sparse planar graphs, SIAM J. Discrete Math. 24(4) (2010) 1572-1583.
Meyer, W., Equitable coloring, Amer. Math. Monthly 80 (1973), 920-922.
Zhang, X., Wu, J.-L., On equitable and equitable list colorings of series-parallel graphs, Discrete Mathematics 311 (2011), 800-803.
Downloads
Published
Issue
Section
License
Copyright (c) 2014 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
