Packing and covering triangles in K₄-free planar graphs

DOI10.1007/S00373-011-1071-9MaRDI QIDQ1926019zbMATH OpenOpenAlexFDO

Authors Penny Haxell, Alexandr Kostochka, Stéphan Thomassé

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-1071-9

zbMATH Keywords

planartriangle packing and coveringTuza's conjecture

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Packing triangles in \(K_4\)-free graphs
• Packing and covering triangles in planar graphs
• Triangle packings and transversals of some \(K_{4}\)-free graphs
• Packing and covering triangles in graphs
• Packing and covering triangles in tripartite graphs
• On triangulating planar graphs under the four-connectivity constraint
• On triangulating planar graphs under the four-connectivity constraint
• Packing triangles in a graph and its complement
• Packing and covering immersions in 4-edge-connected graphs
• Optimal packings and coverings of complete multigraph \(\lambda {K_v}\) with four kinds of graphs

Cites work

• A conjecture on triangles of graphs
• A stability theorem on fractional covering of triangles by edges
• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• On a conjecture of Tuza about packing and covering of triangles
• Packing and covering triangles in graphs
• Packing and covering triangles in planar graphs
• Packing and covering triangles in tripartite graphs
• Packing triangles in weighted graphs
• Some Ramsey-Type Numbers and the Independence Ratio

Cited in

(24)

• The maximum number of triangles in a \(K_4\)-free graph
• On the triangle graph of a \(K(1,2,3)\)-free maximal planar graph
• A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\)
• Packing triangles in \(K_4\)-free graphs
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Packing and covering directed triangles asymptotically
• Triangle packing and covering in dense random graphs
• Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
• Packing and covering directed triangles
• Tuza's conjecture for graphs with maximum average degree less than 7
• 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
• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• Total dual integrality of triangle covering
• Clique polynomials of 2-connected K₅-free chordal graphs
• A Turán-type generalization of Tuza's triangle edge cover problem
• Maximal \(k\)-edge-colorable subgraphs, Vizing's theorem, and Tuza's conjecture
• On Tuza's conjecture for triangulations and graphs with small treewidth
• On Tuza's conjecture for triangulations and graphs with small treewidth
• Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
• On Tuza's conjecture in dense graphs
• Covering triangles in edge-weighted graphs
• Packing and covering triangles in planar graphs

This page was built for publication: Packing and covering triangles in \(K_{4}\)-free planar graphs

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