dorsal/arxiv
View SchemaBipartite Tur\'an problem on cographs
| Authors | Jakob Paul Zimmermann |
|---|---|
| Categories | |
| ArXiv ID | 2601.07406vv1 |
| 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": "557634da-0ac0-4e01-ba64-aa57fb7779f0",
"date_created": "2026-02-17T05:53:12.073000Z",
"date_modified": "2026-02-17T05:53:12.073000Z",
"file_hash": "4e9990fcf8c5e640087d07b495db1d357439593d89fc08453efd23bb304fc794",
"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": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8703261a-d38f-496d-8ab8-3d4ef804aa34",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}