Đang chuẩn bị liên kết để tải về tài liệu:
A note on R-equitable K-colorings of trees

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. | Yugoslav Journal of Operations Research 24 (2014) Number 2, 293 - 298 DOI: 10.2298/YJOR130704039H A NOTE ON R-EQUITABLE K-COLORINGS OF TREES Alain HERTZ Ecole Polytechnique de Montr´eal and GERAD Montr´eal, Canada alain.hertz@gerad.ca Bernard RIES PSL, Universit´e Paris-Dauphine 75775 Paris Cedex 16, France CNRS, LAMSADE UMR 7243 bernard.ries@dauphine.fr Received: July 2013 / Accepted: November 2013 Abstract: 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. Keywords: Trees, equitable coloring, independent sets. MSC: 05C15, 05C69. 1 INTRODUCTION All graphs in this paper are finite, simple and loopless. Let G = (V, E) be a graph. We denote by |G| its order, i.e, the number of vertices in G. For a vertex v ∈ V , let N (v) denote the set of vertices in G that are adjacent to v. N (v) is called the neighborhood of v and its elements are neighbors of v. The degree of vertex v, denoted by deg(v), is the number of neighbors of v, i.e., deg(v) = |N (v)|. ∆(G) denotes the maximum degree of G, i.e., ∆(G) = max{deg(v)| v ∈ V }. For a set V 0 ⊆ V , we denote by G − V 0 the graph obtained from G by deleting all vertices in V 0 as well as all edges incident to at least one vertex of V 0 . An independent set in a graph G = (V, E) is a set S ⊆ V of pairwise nonadjacent vertices. The maximum size of an independent set in a graph G = (V, E) is called the independence number of G and denoted by α(G). A k-coloring c of a graph G = (V, E) is a partition of V into k independent sets which we will denote by V1 (c), V2 (c), · · · , Vk (c) and refer to as color classes. 294 A.Hertz, B.Ries / A Note On r-equitable k-colorings