Abstract:
A
cograph
is a graph that contains no induced path \(P_4\) on four vertices or equivalently a graph that can be constructed from vertices by
sum
and
product
operations.
We study the bipartite Turán problem restricted to cographs: for fixed integers \(s \leq t\), what is the maximum number of edges in an \(n\)-vertex cograph that does not contain \(K_{s,t}\) as a subgraph?
This problem falls within the framework of induced Tur\'an numbers \(\text{ex}(n, \{K_{s,t}, P_4\text{-ind}\})\) introduced by Loh, Tait, Timmons, and Zhou.
Our main result is a
Pumping Theorem
: for every \(s\le t\) there exists a period \(R\) and
core
cographs such that for all sufficiently large \(n\) an extremal cograph is obtained by repeatedly
pumping
one designated pumping component inside the appropriate core (depending on \(n\bmod R\)). We determine the linear coefficient of \(\text{ex}(n, \{K_{s,t}, P_4\text{-ind}\})\) to be \(s-1 + \frac{t-1}{2}\). Moreover, the pumping components are \((t-1)\)-regular and have \(s-1\) common neighbours in the respecitve core graphs, giving the extremal cographs a particularly rigid extremal star-like shape.
Motivated by the rarity of complete classification of extremal configurations, we completely classify all \(K_{3,3}\)-free extremal cographs by proof. We also develop a dynamic programming algorithm for enumerating extremal cographs for small \(n\).
|