Skip to Main content Skip to Navigation
Journal articles

Cooperative colorings of trees and of bipartite graphs

Abstract : Given a system (G 1 ,. .. , G m) of graphs on the same vertex set V , a cooperative coloring is a choice of vertex sets I 1 ,. .. , I m , such that I j is independent in G j and m j=1 I j = V. For a class G of graphs, let m G (d) be the minimal m such that every m graphs from G with maximum degree d have a cooperative coloring. We prove that Ω(log log d) m T (d) O(log d) and Ω(log d) m B (d) O
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Tuesday, March 3, 2020 - 4:18:32 PM
Last modification on : Thursday, January 6, 2022 - 2:50:02 PM
Long-term archiving on: : Thursday, June 4, 2020 - 5:33:13 PM


Files produced by the author(s)


  • HAL Id : hal-02497425, version 1



Ron Aharoni, Eli Berger, Maria Chudnovsky, Frédéric Havet, Zilin Jiang. Cooperative colorings of trees and of bipartite graphs. The Electronic Journal of Combinatorics, Open Journal Systems, 2020. ⟨hal-02497425⟩



Les métriques sont temporairement indisponibles