Generalized line graphs: Cartesian products and complexity of recognition

zbMATH Open1323.05109MaRDI QIDQ888591FDOQ888591

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

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

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

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)

Cites Work

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

Cited In (10)

• A survey of the studies on Gallai and anti-Gallai graphs
• Title not available (Why is that?)
• The recognition problem for line bigraphs
• Recognizing Cartesian products in linear time
• Perfect k‐line graphs and k‐total graphs
• Induced cycles in triangle graphs
• On the hardness of recognizing triangular line graphs
• EULERIAN AND HAMILTONIAN PROPERTIES OF GALLAI AND ANTI-GALLAI TOTAL GRAPHS
• Gallai graphs and anti-Gallai graphs
• Triangle packings and transversals of some \(K_{4}\)-free 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)