Premium
Partitioning a graph into monochromatic connected subgraphs
Author(s) -
Girão António,
Letzter Shoham,
Sahasrabudhe Julian
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22435
Subject(s) - monochromatic color , combinatorics , mathematics , conjecture , degree (music) , graph , connectivity , discrete mathematics , physics , optics , acoustics
We show that every 2 ‐edge‐colored graph on n vertices with minimum degree at least2 n − 5 3 can be partitioned into two monochromatic connected subgraphs, provided n is sufficiently large. This minimum degree condition is tight and the result proves a conjecture of Bal and DeBiasio. We also make progress on another conjecture of Bal and DeBiasio on covering graphs with large minimum degree with monochromatic components of distinct colors.