On generating triangle-free graphs

DOI10.1016/J.ENDM.2009.02.008MaRDI QIDQ2839211zbMATHOpenAlexFDO

Authors Daniel Brügmann, Christian Komusiewicz, Hannes Moser

Publication date 4 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2009.02.008

zbMATH Keywords

kernelizationNP-complete problemparameterized algorithmics

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Triangle edge deletion on planar glasses-free RGB-digraphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Triangle-free planar graphs with small independence number
• On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
• Two edge modification problems without polynomial kernels

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Problem Kernelization for Graph Packing
• Approximating Maximum Subgraphs without Short Cycles
• Automated generation of search tree algorithms for hard graphs modification problems
• Edge-Deletion Problems
• Finding and counting given length cycles
• Kernelization Algorithms for d-Hitting Set Problems

Cited in

(23)

• Testing Triangle-Freeness in General Graphs
• A discharging method: improved kernels for edge triangle packing and covering
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Two edge modification problems without polynomial kernels
• Kernelization for edge triangle packing and covering via a discharging method
• Kernelization for cycle transversal problems
• On the small cycle transversal of planar graphs
• On the small cycle transversal of planar graphs
• A balm: defend the clique-based attack from a fundamental aspect
• Two edge modification problems without polynomial kernels
• Triangle edge deletion on planar glasses-free RGB-digraphs
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• Polynomial kernelization for removing induced claws and diamonds
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
• A survey of parameterized algorithms and the complexity of edge modification
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Kernel for \(K_t\)\textsc-free Edge Deletion
• Feedback edge sets in temporal graphs
• Generating weakly triangulated graphs
• New kernels for several problems on planar graphs
• The parameterized complexity and kernelization of resilience for database queries

This page was built for publication: On generating triangle-free graphs

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