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 metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-02497425
Contributor : Frederic Havet <>
Submitted on : Tuesday, March 3, 2020 - 4:18:32 PM
Last modification on : Tuesday, May 26, 2020 - 6:50:53 PM
Document(s) archivé(s) le : Thursday, June 4, 2020 - 5:33:13 PM

File

ejc-cooperative_coloring.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02497425, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

65

Files downloads

108