Tuza's conjecture for binary geometries

DOI10.1137/22M1511229MaRDI QIDQ6385450zbMATH OpenFDO

Authors Kazuhiro Nomoto, J. G. van der Pol

Publication date 12 December 2021

Full work available at URL https://doi.org/10.1137/22M1511229

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Tuza (A conjecture, in Proceedings of the Colloquia Mathematica Societatis Janos Bolyai, 1981) conjectured that $au(G)le2u(G)$ for all graphs $G$, where $au(G)$ is the minimum size of an edge set whose removal makes $G$ triangle-free, and $u(G)$ is the maximum size of a collection of pairwise edge-disjoint triangles. Here, we generalise Tuza's conjecture to simple binary matroids that do not contain the Fano plane as a restriction. We prove that the geometric version of the conjecture holds for cographic matroids.

Recommendations

• On Tuza's conjecture for triangulations and graphs with small treewidth
• On Tuza's conjecture for triangulations and graphs with small treewidth
• A generalization of Tuza's conjecture
• On a conjecture of Tuza about packing and covering of triangles
• Tuza's Conjecture for Threshold Graphs

This page was built for publication: Tuza's conjecture for binary geometries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6385450)