Reconstructing a graph from its arc incidence graph

DOI10.1007/s00373-011-1073-7zbMath1256.05152MaRDI QIDQ1926018

Stephen G. Hartke, Geir T. Helleloid

Publication date: 27 December 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-011-1073-7

zbMATH Keywords

reconstruction algorithm; incidence graph; arc incidence graph; incidence coloring conjecture

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

On the hardness of recognizing triangular line graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some properties of line digraphs
• A labeling algorithm to recognize a line digraph and output its root graph
• Incidence and strong edge colorings of graphs
• The incidence coloring conjecture for graphs of maximum degree 3
• Incidence coloring of \(k\)-degenerated graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A Note on Incidence graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• On Eulerian and Hamiltonian Graphs and Line Graphs
• The interchange graph of a finite graph
• On Hamiltonian Line-Graphs
• Characterizations of derived graphs