The existence of homeomorphic subgraphs in chordal graphs
type: Item
instance of: scholarly article
title: The existence of homeomorphic subgraphs in chordal graphs
zbMATH Open document ID: 0883.05117
DOI: 10.1016/S0893-9659(97)00027-X
author: C. R. Subramanian
author: C. E. Veni Madhavan
published in: Applied Mathematics Letters
publication date: 1998-02-23T00:00:00Z
review text: Let \(H\) be a complete graph \(K_s\), \(s \geq 3\), a complete bipartite graph \(K_{s,t}\), \(s,t \geq 2\), or a wheel \(W_s\), \(s \geq 3\). Then a chordal graph \(G\) contains a subgraph homeomorphic to \(H\) if and only if \(G\) contains a subgraph isomorphic to \(H\). Furthermore, if \((v_1,v_2,\dots,v_n)\) is a perfect elimination ordering of \(G\), then \(G\) is planar if and only if \(|N(v_i) \cap \{v_{i+1},\dots,v_n\}|\leq 3\) and in case of equality there is at most one vertex in \(\{v_{i+1},\dots,v_n\}\) adjacent to all vertices of \(N(v_i) \cap \{v_{i+1},\dots,v_n\}\) for \(i=1,\dots,n\). This leads to an simple linear time algorithm for recognizing planar chordal graphs.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1085354
zbMATH Keywords: chordal graph
zbMATH Keywords: planar graph
zbMATH Keywords: graph homeomorphism
zbMATH Keywords: graph isomorphism
MaRDI profile type: Publication
cites work: Parallel concepts in graph theory
cites work: Efficient Planarity Testing
cites work: Q3328583
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: The subgraph homeomorphism problem for small wheels
cites work: Disjoint Paths—A Survey
cites work: Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
description: scientific article; zbMATH DE number 1085354