Cooperative colorings of trees and of bipartite graphs

Ron Aharoni, Eli Berger, Maria Chudnovsky, Frédéric Havet, Zilin Jiang

Research output: Contribution to journalArticle

Abstract

Given a system (G1, …, Gm) of graphs on the same vertex set V, a cooperative coloring is a choice of vertex sets I1, …, Im, such that Ij is independent in Gj and (formula presented)m j=1Ij = V . For a class G of graphs, let mG (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) ≤ mT (d) ≤ O(log d) and Ω(log d) ≤ mB(d) ≤ O(d/ log d), where T is the class of trees and B is the class of bipartite graphs.

Original languageEnglish (US)
Article numberP1.41
JournalElectronic Journal of Combinatorics
Volume27
Issue number1
DOIs
StatePublished - 2020

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Cooperative colorings of trees and of bipartite graphs'. Together they form a unique fingerprint.

  • Cite this