An internal or friendly partition of a graph is a partition of the vertices into
two nonempty sets A∪B so that every vertex has at least as many neighbours in its
own class as in the other one. For regular graphs, this means |N(v)∩A| ≥ deg(v)/2
for all elements v ∈ A and |N(v) ∩ B| ≥ deg(v)/2 for all elements v ∈ B. An old
conjecture attributed to DeVos states that for fixed d, such a partition exists for
all
d-regular graphs, apart from finitely many counterexamples. This has been resolved
for d ∈ {3, 4, 6}. (We remark that this is also closely related to an conjecture of
Zolt´an F¨uredi, on friendly bisection of the Erd˝os-R´enyi random graph).
In this talk I will give a survey of related results and highlight the following contributions,
mostly related to the open d = 5 case:
Theorem 0.0.8 In each n-vertex 5-regular graph, the intersection of 3-cohesive sets
with minimum size contains at most n/4 + 1 vertices.
Here the term k-cohesive was introduced by Ban and Linial [?] for vertex sets
spanning a graph of minimum degree at least k. Note that for 5-regular graph
admitting friendly partitions, the intersection of 3-cohesive sets with minimum size
contains exactly zero vertices. The result relies on the combination of algebraic
techniques (the Alon-Friedland-Kalai theorem, an application of the Combontorial
Nullstellensatz) with combinatorial and random techniques.
40
Theorem 0.0.9 Asymptotically almost every 5-regular graph has an internal (friendly)
partition.
This would follow from a strengthening of the upper bound of the minimum
bisection width problem for 5-regular random graphs, and refines the random process
of Diaz, Serna and Wormald and their differential equation method as well.
Finally we study the problem for the incidence graphs of projective planes, show
several connections and applications, and point out the possible room for improvement
in finding partitions where the spanning graphs of the two parts have minimum
degree greater than the half of the average degree.
The talk is based on a project joint work with P. Barnkopf, Z. Paulovics, E.
Csóka, P. Fekete, L. Szemerédi.
