Geodesic
Cooperative colorings of trees and of bipartite graphs
Ron Aharoni1 ; Eli Berger2 ; Maria Chudnovsky3 ; Frédéric Havet4 ; Zilin Jiang5
1Technion – Israel Institute of Technology
2University of Haifa
3Princeton University
4CNRS, Université Côte d’Azur, I3S, and INRIA
5Massachusetts Institute of Technology
The electronic journal of combinatorics, Tome 27 (2020) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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}^{m}I_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.
DOI : 10.37236/8111
Classification : 05C15, 05C69, 05C05
Mots-clés : bipartite graphs

Ron Aharoni  1   ; Eli Berger  2   ; Maria Chudnovsky  3   ; Frédéric Havet  4   ; Zilin Jiang  5

1 Technion – Israel Institute of Technology
2 University of Haifa
3 Princeton University
4 CNRS, Université Côte d’Azur, I3S, and INRIA
5 Massachusetts Institute of Technology 
@article{10_37236_8111,
     author = {Ron Aharoni and Eli Berger and Maria Chudnovsky and Fr\'ed\'eric Havet and Zilin Jiang},
     title = {Cooperative colorings of trees and of bipartite graphs},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {1},
     doi = {10.37236/8111},
     zbl = {1432.05036},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8111/}
}
TY  - JOUR
AU  - Ron Aharoni
AU  - Eli Berger
AU  - Maria Chudnovsky
AU  - Frédéric Havet
AU  - Zilin Jiang
TI  - Cooperative colorings of trees and of bipartite graphs
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8111/
DO  - 10.37236/8111
ID  - 10_37236_8111
ER  - 
%0 Journal Article
%A Ron Aharoni
%A Eli Berger
%A Maria Chudnovsky
%A Frédéric Havet
%A Zilin Jiang
%T Cooperative colorings of trees and of bipartite graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8111/
%R 10.37236/8111
%F 10_37236_8111
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, Tome 27 (2020) no. 1. doi: 10.37236/8111

Cité par Sources :