Induced cycles in triangle graphs

详细信息    查看全文

• 作者：Aparna Lakshmanan S^a ; ^{aparnaren@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Csilla Bujtá ; s^b ; ^c ; ^{bujtas@dcs.uni-pannon.hu" class="auth_mail" title="E-mail the corresponding author} ; Zsolt Tuza^b ; ^c ; ^{tuza@dcs.uni-pannon.hu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Triangle graph ; FF-free graph ; Perfect graph ; Tuza&rsquo ; s Conjecture
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 August 2016
• 年：2016
• 卷：209
• 期：Complete
• 页码：264-275
• 全文大小：410 K

文摘

The triangle graph of a graph G$G$, denoted by T(G)$\mathcal{T}\left(G\right)$, is the graph whose vertices represent the triangles (K₃$K_3$ subgraphs) of G$G$, and two vertices of T(G)$\mathcal{T}\left(G\right)$ are adjacent if and only if the corresponding triangles share an edge. In this paper, we characterize graphs whose triangle graph is a cycle and then extend the result to obtain a characterization of C_n$C_n$-free triangle graphs. As a consequence, we give a forbidden subgraph characterization of graph G$G$ for which T(G)$\mathcal{T}\left(G\right)$ is a tree, a chordal graph, or a perfect graph. For the class of graphs whose triangle graph is perfect, we verify a conjecture of the third author concerning packing and covering of triangles.