Generalized line graphs: Cartesian products and complexity of recognition

MaRDI QIDQ888591zbMATH OpenFDO

Authors 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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

triangle graphCartesian product 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)

Recommendations

• Perfect k‐line graphs and k‐total graphs
• Path graphs
• On the hardness of recognizing triangular line graphs
• scientific article; zbMATH DE number 992948
• Iterated k-line graphs

Cites work

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

Cited in

(10)

• The recognition problem for line bigraphs
• Recognizing Cartesian products in linear time
• Gallai graphs and anti-Gallai graphs
• Triangle packings and transversals of some \(K_{4}\)-free graphs
• Perfect k‐line graphs and k‐total graphs
• On the hardness of recognizing triangular line graphs
• scientific article; zbMATH DE number 38312 (Why is no real title available?)
• EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS
• A survey of the studies on Gallai and anti-Gallai graphs
• Induced cycles in triangle graphs

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

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