Edge partitions into induced-$2K_2$-free bipartite graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908858535903232 |
|---|---|
| author | London, András |
| author_facet | London, András |
| contents | We study edge partitions of a bipartite graph into induced-$2K_2$-free bipartite graphs, i.e.\ into Ferrers (chain) graphs. We define $\fp(G)$ as the minimum number of parts in such a partition. We prove general lower and upper bounds in terms of induced matchings and Dilworth widths of neighborhood posets. We compute the parameter exactly for paths and even cycles, and we exhibit separations showing that the induced-matching lower bound and the width upper bound can both be far from tight. We also record a simple host-induced conflict-graph lower bound, present a $0$--$1$ matrix viewpoint, and add some complexity remarks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_00593 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Edge partitions into induced-$2K_2$-free bipartite graphs London, András Combinatorics 05C70, 05C75, 06A07, 15B34 We study edge partitions of a bipartite graph into induced-$2K_2$-free bipartite graphs, i.e.\ into Ferrers (chain) graphs. We define $\fp(G)$ as the minimum number of parts in such a partition. We prove general lower and upper bounds in terms of induced matchings and Dilworth widths of neighborhood posets. We compute the parameter exactly for paths and even cycles, and we exhibit separations showing that the induced-matching lower bound and the width upper bound can both be far from tight. We also record a simple host-induced conflict-graph lower bound, present a $0$--$1$ matrix viewpoint, and add some complexity remarks. |
| title | Edge partitions into induced-$2K_2$-free bipartite graphs |
| topic | Combinatorics 05C70, 05C75, 06A07, 15B34 |
| url | https://arxiv.org/abs/2603.00593 |