Cooperative coloring of some graph families

In a family G1,G2,…,Gm of graphs sharing the same vertex set V, a cooperative coloring involves selecting one independent set Ii from Gi for each i∈{1,2,…,m} such that ⋃i=1mIi=V. For a graph class G, let mG(d) denote the minimum m required to ensure that any graph family G1,G2,…,Gm on the same verte...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2024-07, Vol.347 (7), p.113973, Article 113973
Main Authors: Bai, Xuqing, Li, Bi, Xu, Chuandong, Zhang, Xin
Format: Article
Language:English
Subjects:
Adapted coloring
Cooperative coloring
Trees
Wheels
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In a family G1,G2,…,Gm of graphs sharing the same vertex set V, a cooperative coloring involves selecting one independent set Ii from Gi for each i∈{1,2,…,m} such that ⋃i=1mIi=V. For a graph class G, let mG(d) denote the minimum m required to ensure that any graph family G1,G2,…,Gm on the same vertex set, where Gi∈G and Δ(Gi)≤d for each i∈{1,2,…,m}, admits a cooperative coloring. For the graph classes T (trees) and W (wheels), we find that mT(3)=4 and mW(4)=5. Also, we prove that mB⁎(d)=O(log2⁡d) and mL(d)=O(log⁡dlog⁡log⁡d), where B⁎ represents the class of graphs whose components are balanced complete bipartite graphs, and L represents the class of graphs whose components are generalized theta graphs.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2024.113973