EUVIMEDEUVIMED entdecken
Crossref

Edge partitions into induced-2K2-free bipartite graphs

András London

Ars Combinatoria · 14.03.2026 · 166 · 15-26

DOI: 10.61091/ars166-02 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Ars Combinatoria, online erschienen am 14.03.2026. Verfasst von András London.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study edge partitions of a bipartite graph into induced-2K2-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.

Zitieren

APA

London, A. (2026). Edge partitions into induced-2K2-free bipartite graphs. Ars Combinatoria, 166, 15-26. https://doi.org/10.61091/ars166-02

Vancouver

London A. Edge partitions into induced-2K2-free bipartite graphs. Ars Combinatoria. 2026;166:15-26. doi:10.61091/ars166-02

BibTeX
@article{London2026,
  author = {London, András},
  title = {Edge partitions into induced-2K2-free bipartite graphs},
  journal = {Ars Combinatoria},
  year = {2026},
  volume = {166},
  pages = {15--26},
  doi = {10.61091/ars166-02}
}
Kostenlos starten →