dorsal/arxiv
View SchemaBipartite Tur\'an problem on cographs
| Authors | Jakob Paul Zimmermann |
|---|---|
| Categories | |
| ArXiv ID | 2601.07406vv2 |
| URL | https://arxiv.org/abs/2601.07406 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
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\'an 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$.
{
"annotation_id": "d5ee03fc-dc10-4f06-a862-151a0cba1618",
"date_created": "2026-02-17T05:53:12.062000Z",
"date_modified": "2026-02-17T05:53:12.062000Z",
"file_hash": "22e3fcc84cb6c60514a88f57199ddc9e0a7753f2fa578e9169421639f093a6bc",
"private": false,
"record": {
"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\\\u0027an 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\\\u0027an numbers $\\text{ex}(n, \\{K_{s,t}, P_4\\text{-ind}\\})$ introduced by Loh, Tait, Timmons, and Zhou.\n 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.\n 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$.",
"arxiv_id": "2601.07406",
"authors": [
"Jakob Paul Zimmermann"
],
"categories": [
"math.CO"
],
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Bipartite Tur\\\u0027an problem on cographs",
"url": "https://arxiv.org/abs/2601.07406",
"version": "v2"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4e94028e-6e6e-45b1-9d33-418fc77e070c",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}