Disjoint induced subgraphs of the same order and size

2013/12/05 by Bollobás, Béla, Kittipassorn, Teeradej, Narayanan, Bhargav +1
#05C35 (Primary) 05C07 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1312.1680

Abstract

For a graph G, let f(G) be the largest integer k for which there exist two vertex-disjoint induced subgraphs of G each on k vertices, both inducing the same number of edges. We prove that f(G) ≥ n/2 - o(n) for every graph G on n vertices. This answers a question of Caro and Yuster.

Related

• Large induced subgraphs with k vertices of almost maximum degree
• Every graph contains a linearly sized induced subgraph with all degrees odd
• The confirmation of a conjecture on disjoint cycles in a graph
• Edge-disjoint cycles with the same vertex set
• Induced subgraphs with many repeated degrees