## Abstract

Two subgraphs A,B of a graph G are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erdős in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results. We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number: that is, for all t,c≥1 there exists d≥1 such that if G has chromatic number at least d, and does not contain the complete graph K_{t} as a subgraph, then there are anticomplete subgraphs A,B, where A has minimum degree at least c and B has chromatic number at least c. Second, we look at what happens if we replace the hypothesis that G has sufficiently large chromatic number with the hypothesis that G has sufficiently large minimum degree. This, together with excluding K_{t}, is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding K_{t} we exclude the complete bipartite graph K_{t,t}. More exactly: for all t,c≥1 there exists d≥1 such that if G has minimum degree at least d, and does not contain the complete bipartite graph K_{t,t} as a subgraph, then there are two anticomplete subgraphs both with minimum degree at least c.

Original language | English (US) |
---|---|

Pages (from-to) | 211-222 |

Number of pages | 12 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 165 |

DOIs | |

State | Published - Mar 2024 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Chromatic number
- Subgraphs