The existence of homeomorphic subgraphs in chordal graphs (Q1372257): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:07, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The existence of homeomorphic subgraphs in chordal graphs |
scientific article |
Statements
The existence of homeomorphic subgraphs in chordal graphs (English)
0 references
23 February 1998
0 references
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.
0 references
chordal graph
0 references
planar graph
0 references
graph homeomorphism
0 references
graph isomorphism
0 references