Tuza's conjecture is an unsolved problem in graph theory concerning triangles in undirected graphs. It holds that in any graph it is possible to remove at most twice as many edges as the maximum triangle packing size and eliminate all triangles, with the complete graph K5 an extreme case that requires exactly twice the packing size. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementFor every graph G, the minimum number of edges needed to intersect every triangle, written tau(G), is at most twice the maximum number of edge disjoint triangles, written nu(G). 1 Proposed Year Progress Toward ResolutionThe conjecture remains unproven in general, though it has been verified for planar graphs and several other graph classes and improved general bounds have been established. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Tuza's Conjecture (Wikipedia)
Sources
1. Tuza's Conjecture (Wikipedia)
Formal statement section
τ(G) ≤ 2ν(G)
Current status section
remains unproven.
- Lead section
View the Source2. Tuza's Conjecture (Wikipedia)
Wikimedia FoundationLead section
Tuza's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning triangles in undirected graphs.
History and partial results section
Zsolt Tuza formulated Tuza's conjecture in 1981.
In Branch: Graph Theory, Lead sentence
Tuza's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning triangles in undirected graphs.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.