On generating triangle-free graphs
From MaRDI portal
Publication:2839211
DOI10.1016/J.ENDM.2009.02.008zbMATH Open1267.05246OpenAlexW2081072149MaRDI QIDQ2839211FDOQ2839211
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10)
Cites Work
- Automated generation of search tree algorithms for hard graphs modification problems
- A Problem Kernelization for Graph Packing
- Title not available (Why is that?)
- Finding and counting given length cycles
- Kernelization Algorithms for d-Hitting Set Problems
- Edge-Deletion Problems
- Approximating Maximum Subgraphs without Short Cycles
Cited In (24)
- Kernelization for edge triangle packing and covering via a discharging method
- Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
- Parameterizing edge modification problems above lower bounds
- The parameterized complexity and kernelization of resilience for database queries
- Kernelization for cycle transversal problems
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Cutting a tree with subgraph complementation is hard, except for some small trees
- A discharging method: improved kernels for edge triangle packing and covering
- On the small cycle transversal of planar graphs
- Two edge modification problems without polynomial kernels
- Cutting a tree with subgraph complementation is hard, except for some small trees
- Kernel for \(K_t\)\textsc-free Edge Deletion
- Testing Triangle-Freeness in General Graphs
- A survey of parameterized algorithms and the complexity of edge modification
- On the small cycle transversal of planar graphs
- Two edge modification problems without polynomial kernels
- Feedback edge sets in temporal graphs
- New kernels for several problems on planar graphs
- Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- Triangle edge deletion on planar glasses-free RGB-digraphs
- Polynomial kernelization for removing induced claws and diamonds
- Generating weakly triangulated graphs
- A balm: defend the clique-based attack from a fundamental aspect
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)
