Cooperative colorings of trees and of bipartite graphs (Q2294110)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Cooperative colorings of trees and of bipartite graphs
scientific article

    Statements

    Cooperative colorings of trees and of bipartite graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    10 February 2020
    0 references
    Summary: Given a system \((G_1, \ldots ,G_m)\) of graphs on the same vertex set \(V\), a cooperative coloring is a choice of vertex sets \(I_1, \ldots ,I_m\), such that \(I_j\) is independent in \(G_j\) and \(\bigcup_{j=1}^mI_j = V\). For a class \(\mathcal{G}\) of graphs, let \(m_{\mathcal{G}}(d)\) be the minimal \(m\) such that every \(m\) graphs from \(\mathcal{G}\) with maximum degree \(d\) have a cooperative coloring. We prove that \(\Omega(\log\log d) \le m_\mathcal{T}(d) \le O(\log d)\) and \(\Omega(\log d)\le m_\mathcal{B}(d) \le O(d/\log d)\), where \(\mathcal{T}\) is the class of trees and \(\mathcal{B}\) is the class of bipartite graphs.
    0 references
    bipartite graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references