Recognition of linear and star variants of leaf powers is in P

DOI10.1007/978-3-031-15914-5_6arXiv2105.12407OpenAlexW4312735532MaRDI QIDQ6043183

Jan Arne Telle, Svein Høgemo, Martin Vatshelle, Bergougnoux Benjamin

Publication date: 5 May 2023

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

interval graphsleaf powerco-threshold tolerance graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Recognizing k -Leaf Powers in Polynomial Time, for Constant k

Cites Work

• Unnamed Item
• Towards a characterization of leaf powers by clique arrangements
• On recognition of threshold tolerance graphs and their complements
• Parameterized leaf power recognition via embedding into graph products
• Structure and linear time recognition of 3-leaf powers
• Rooted directed path graphs are leaf powers
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On strongly chordal graphs that are not leaf powers
• Neighborhood subtree tolerance graphs
• The 4-Steiner Root problem
• Mim-width. III. Graph powers and generalized distance domination problems
• Co-TT graphs and a characterization of split co-TT graphs
• On Graph Powers for Leaf-Labeled Trees
• Pairwise Compatibility Graphs: A Survey
• A Class of Balanced Matrices Arising from Location Problems
• The 3-Steiner Root Problem
• Threshold tolerance graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Structure and linear-time recognition of 4-leaf powers
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Recognition of linear and star variants of leaf powers is in P