Testing Triangle-Freeness in General Graphs

DOI10.1137/07067917XMaRDI QIDQ3629476zbMATH OpenOpenAlexFDO

Authors Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron

Publication date 27 May 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/07067917x

zbMATH Keywords

approximation algorithmsCayley graphsproperty testingrandomized algorithmssubgraph-freenesstriangle-freeness

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• On generating triangle-free graphs
• The diagnosability of triangle-free graphs
• scientific article; zbMATH DE number 850231
• scientific article; zbMATH DE number 1208712
• scientific article; zbMATH DE number 5917767
• On existentially complete triangle-free graphs
• The generation of maximal triangle-free graphs
• scientific article; zbMATH DE number 1347014
• On maximal triangle‐free graphs
• Generalizations of triangulated graphs

Cited in

(17)

• Minimizing the two-round Even-Mansour cipher
• Lower bounds for testing triangle-freeness in Boolean functions
• Lower bounds for approximating graph parameters via communication complexity
• A generalized Turán problem and its applications
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• On the multiparty communication complexity of testing triangle-freeness
• Lower bounds for testing triangle-freeness in Boolean functions
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• Faster Property Testers in a Variation of the Bounded Degree Model
• Faster property testers in a variation of the bounded degree model
• (Quantum) complexity of testing signed graph clusterability
• Testing C_k-freeness in bounded-arboricity graphs
• Testing triangle freeness in the general model in graphs with arboricity \(O(\sqrt{n})\)
• Results on H-freeness testing in graphs of bounded r-admissibility
• Tolerant testers for subgraph-freeness
• Testing C_k-freeness in bounded admissibility graphs

This page was built for publication: Testing Triangle-Freeness in General Graphs

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