Cooperative colorings of trees and of bipartite graphs
Résumé
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
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...