2010/07/07 by Pranav Anand, Henry Escuadro, Anand, Pranav +7
Computer Science · Mathematics · #05C76 #1-planar graph #Advanced Graph Theory Research #Block graph #Chordal graph #Cograph #Combinatorics #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete mathematics #F.2.2 #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Indifference graph #Line graph #Mathematics #Maximal independent set #Pathwidth #Split graph #Vertex (graph theory) #acm:05C76 #math.CO #msc:05C76
paper · pdf · doi:10.48550/arxiv.1007.1178
18 pages, 8 figures, 4 tables
arxiv created 2010/07/07 · openalex publication_date 2010/07/07 · arxiv updated 2010/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
Given a graph G, its triangular line graph is the graph T(G) with vertex set consisting of the edges of G and adjacencies between edges that are incident in G as well as being within a common triangle. Graphs with a representation as the triangular line graph of some graph G are triangular line graphs, which have been studied under many names including anti-Gallai graphs, 2-in-3 graphs, and link graphs. While closely related to line graphs, triangular line graphs have been difficult to understand and characterize. Van Bang Le asked if recognizing triangular line graphs has an efficient algorithm or is computationally complex. We answer this question by proving that the complexity of recognizing triangular line graphs is NP-complete via a reduction from 3-SAT.