The existence of homeomorphic subgraphs in chordal graphs (Q1372257): Difference between revisions

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.