On the hardness of recognizing triangular line graphs

DOI10.1016/j.disc.2011.11.037zbMath1408.68066arXiv1007.1178OpenAlexW1991938654MaRDI QIDQ442382

J. Herrera, H. S. Yoon

Publication date: 10 August 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessH-line graphtriangular line graph

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)

Related Items (9)

Gallai and anti-Gallai graph operators ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Generalized line graphs: Cartesian products and complexity of recognition ⋮ New results and open problems in line graphs ⋮ Forests and trees among Gallai graphs ⋮ EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS ⋮ Edge clique partition in \((k,\ell)\)-graphs ⋮ On an edge partition and root graphs of some classes of line graphs ⋮ A survey of the studies on Gallai and anti-Gallai graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gallai graphs and anti-Gallai graphs
• Convergence of sequences of iterated triangular line graphs
• Convergent sequences of iterated \(H\)-line graphs
• Reconstructing a graph from its arc incidence graph
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Triangular line graphs and word sense disambiguation
• Gallai and anti-Gallai graphs of a graph
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Transitiv orientierbare Graphen

This page was built for publication: On the hardness of recognizing triangular line graphs