Partitions of Graphs into Special Bipartite Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915636866711552 |
|---|---|
| author | Győrffy, Lajos London, András Nagy, Gábor V. Pluhár, András |
| author_facet | Győrffy, Lajos London, András Nagy, Gábor V. Pluhár, András |
| contents | We study the problem of partitioning the edge set of the complete graph into bipartite subgraphs under certain constraints defined by forbidden subgraphs. These constraints lead to both classical problems, such as partitioning into independent matchings or complete bipartite subgraphs, and novel variants motivated by structural restrictions. Our theoretical framework is inspired by clustering problems in real-world transaction graphs, which can be formulated naturally as edge partitioning problems under bipartite graph constraints.
The main result of this paper is the proof of the bounds for $χ'_{2K_2}(n)$, which corresponds to the minimum number of induced $2K_2$-free bipartite subgraphs needed to partition the edges of $K_n$. In addition to this central result, we also present several similar bounds for other forbidden subgraphs on three or four vertices. Some are included primarily for the sake of completeness, to demonstrate the broad applicability of our approach, and some lead to other novel or well-known graph theoretical problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_12664 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Partitions of Graphs into Special Bipartite Graphs Győrffy, Lajos London, András Nagy, Gábor V. Pluhár, András Combinatorics We study the problem of partitioning the edge set of the complete graph into bipartite subgraphs under certain constraints defined by forbidden subgraphs. These constraints lead to both classical problems, such as partitioning into independent matchings or complete bipartite subgraphs, and novel variants motivated by structural restrictions. Our theoretical framework is inspired by clustering problems in real-world transaction graphs, which can be formulated naturally as edge partitioning problems under bipartite graph constraints. The main result of this paper is the proof of the bounds for $χ'_{2K_2}(n)$, which corresponds to the minimum number of induced $2K_2$-free bipartite subgraphs needed to partition the edges of $K_n$. In addition to this central result, we also present several similar bounds for other forbidden subgraphs on three or four vertices. Some are included primarily for the sake of completeness, to demonstrate the broad applicability of our approach, and some lead to other novel or well-known graph theoretical problems. |
| title | Partitions of Graphs into Special Bipartite Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.12664 |