The existence of homeomorphic subgraphs in chordal graphs (Q1372257): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel concepts in graph theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Efficient Planarity Testing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The subgraph homeomorphism problem for small wheels / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Disjoint Paths—A Survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Color-coding / rank | |||
Normal rank |
Latest revision as of 19:58, 27 May 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