Generalized line graphs: Cartesian products and complexity of recognition

zbMath1323.05109MaRDI QIDQ888591

Aparna Lakshmanan S., Csilla Bujtás, Zsolt Tuza

Publication date: 2 November 2015

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p33

zbMATH Keywords

Cartesian product graphtriangle graphanti-Gallai graph\(k\)-line graph

Mathematics Subject Classification ID

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

Related Items (4)

Induced cycles in triangle graphs ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS ⋮ A survey of the studies on Gallai and anti-Gallai graphs

Cites Work

• Unnamed Item
• On the hardness of recognizing triangular line graphs
• \(K_ i\)-covers. I: Complexity and polytopes
• Gallai graphs and anti-Gallai graphs
• Intersection multigraphs of uniform hypergraphs
• Convergence of sequences of iterated triangular line graphs
• Two characterizations of interchange graphs of complete m-partite graphs
• Old and new generalizations of line graphs
• Small edge sets meeting all triangles of a graph
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Triangular line graphs and word sense disambiguation
• Ki-covers. II.Ki-perfect graphs
• Gallai and anti-Gallai graphs of a graph
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Perfect k‐line graphs and k‐total graphs
• Transitiv orientierbare Graphen
• Characterizations of derived graphs

This page was built for publication: Generalized line graphs: Cartesian products and complexity of recognition