scientific article; zbMATH DE number 7080199

MaRDI QIDQ4968385zbMATH OpenFDO

Authors Berit Grußien

Publication date 12 July 2019

Full work available at URL https://arxiv.org/abs/1802.10331

zbMATH Keywords

canonizationchordal claw-free graphsdescriptive complexityisomorphism problem: logarithmic spacepolynomial time: fixed-point logic

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 7204318
• An approximate version of Hadwiger's conjecture for claw-free graphs
• Linear-time algorithms for eliminating claws in graphs
• Parameterized complexity of induced graph matching on claw-free graphs
• Triangulation and clique separator decomposition of claw-free graphs
• Stable sets in claw-free graphs: a journey through algorithms and polytopes
• Chorded pancyclic properties in claw-free graphs
• On the Erdős-Gyárfás conjecture in claw-free graphs
• Claw-free t-perfect graphs can be recognized in polynomial time
• Bounding the clique-width of H-free chordal graphs

Cited in

(6)

• L-recursion and a new logic for logarithmic space
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• L-recursion and a new logic for logarithmic space
• scientific article; zbMATH DE number 7204318 (Why is no real title available?)
• Intersection graphs of non-crossing paths
• Separating LREC from LFP

This page was built for publication:

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