Small edge sets meeting all triangles of a graph

DOI10.1007/s00373-011-1048-8zbMath1256.05182OpenAlexW2049946846WikidataQ59072576 ScholiaQ59072576MaRDI QIDQ1926043

S. Aparna Lakshmanan, Zsolt Tuza, Csilla Bujtás

Publication date: 27 December 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1048-8

zbMATH Keywords

\(T\)-transversalodd-wheel-free graphstriangle-3-colorable graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15)

Related Items (14)

Induced cycles in triangle graphs ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ Fractional \(K_{4}\)-covers ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Generalized line graphs: Cartesian products and complexity of recognition ⋮ Tuza's Conjecture for Threshold Graphs ⋮ Packing and covering directed triangles ⋮ Total Dual Integrality of Triangle Covering ⋮ EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS ⋮ Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture ⋮ Packing and covering directed triangles asymptotically ⋮ Unnamed Item ⋮ Triangle packing and covering in dense random graphs ⋮ Tuza's conjecture for graphs with maximum average degree less than 7

Cites Work

• Unnamed Item
• A stability theorem on fractional covering of triangles by edges
• The strong perfect graph theorem
• Ryser's conjecture for tripartite 3-graphs
• Packing and covering triangles in planar graphs
• A comment on Ryser's conjecture for intersecting hypergraphs
• Gallai graphs and anti-Gallai graphs
• Intersection multigraphs of uniform hypergraphs
• Packing and covering triangles in graphs
• Packing and covering triangles in tripartite graphs
• Old and new generalizations of line graphs
• On a conjecture of Tuza about packing and covering of triangles
• Covering and independence in triangle structures
• A conjecture on triangles of graphs
• The NP-Completeness of Edge-Coloring
• Perfect Triangle Families
• Packing Triangles in Weighted Graphs

This page was built for publication: Small edge sets meeting all triangles of a graph