Cooperative colorings of trees and of bipartite graphs - Archive ouverte HAL Access content directly
Journal Articles The Electronic Journal of Combinatorics Year : 2020

Cooperative colorings of trees and of bipartite graphs

(1) , (2) , (3) , (4) , (5)
1
2
3
4
5

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
Fichier principal
Vignette du fichier
ejc-cooperative_coloring.pdf (278.76 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02497425 , version 1 (03-03-2020)

Identifiers

  • HAL Id : hal-02497425 , version 1

Cite

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, 2020. ⟨hal-02497425⟩
69 View
96 Download

Share

Gmail Facebook Twitter LinkedIn More