Triangle edge deletion on planar glasses-free RGB-digraphs

DOI10.1016/J.TCS.2018.10.034MaRDI QIDQ2317352zbMATH OpenOpenAlexFDO

Authors Dongjing Miao, Zhipeng Cai, Jiguo Yu, Yingshu Li

Publication date 9 August 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.10.034

zbMATH Keywords

NP-complete problemRGB-digraphstriangle edge deletion

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deleting edges from Ramsey graphs
• Acyclic edge coloring of planar graphs without adjacent triangles
• Acyclic edge coloring of triangle-free planar graphs
• Triangle decompositions of planar graphs
• On acyclic edge coloring of planar graphs without intersecting triangles
• Destroying Bicolored $P_3$s by Deleting Few Edges
• Destroying bicolored \(P_3\)s by deleting few edges
• On edge colorings of 1-planar graphs without adjacent triangles
• Edge colorings of complete graphs without tricolored triangles
• Edge-disjoint rainbow triangles in edge-colored graphs

Cites work

• A fixed-parameter algorithm for the directed feedback vertex set problem
• Automated generation of search tree algorithms for hard graphs modification problems
• Finding and counting given length cycles
• Node-and edge-deletion NP-complete problems
• On generating triangle-free graphs
• On the complexity of sampling query feedback restricted database repair of functional dependency violations

Cited in

(3)

• Destroying bicolored \(P_3\)s by deleting few edges
• On generating triangle-free graphs
• Destroying Bicolored $P_3$s by Deleting Few Edges

This page was built for publication: Triangle edge deletion on planar glasses-free RGB-digraphs

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