Abstract

Given a system (G1,…,Gm)(G_1, \ldots ,G_m) of graphs on the same vertex set VV, a cooperative coloring is a choice of vertex sets I1,…,ImI_1, \ldots ,I_m, such that IjI_j is independent in GjG_j and ⋃j=1mIj=V\bigcup_{j=1}^{m}I_j = V. For a class G\mathcal{G} of graphs, let mG(d)m_{\mathcal{G}}(d) be the minimal mm such that every mm graphs from G\mathcal{G} with maximum degree dd have a cooperative coloring. We prove that Ω(log⁡log⁡d)≤mT(d)≤O(log⁡d)Ω(\log\log d) \le m_\mathcal{T}(d) \le O(\log d) and Ω(log⁡d)≤mB(d)≤O(d/log⁡d)Ω(\log d)\le m_\mathcal{B}(d) \le O(d/\log d), where T\mathcal{T} is the class of trees and B\mathcal{B} is the class of bipartite graphs.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.