Median Graphs and Triangle-Free Graphs
Wilfried Imrich, Sandi Klavžar, Henry Martyn Mulder · SIAM Journal on Discrete Mathematics · 1999
Let M(m,n) be the complexity of checking whether a graph G with medges and n vertices is a median graph. We show that the complexity of checking whether Gis triangle-free is at most O(M(m,m)). Conversely, we prove that the complexity of checking whether a given graph is a median graph is at most O(m log n + T(m log n,n)), where T(m,n) is the complexity of finding all triangles of the graph. We also demonstrate that, intuitively speaking, there are as many median graphs as there are triangle-free graphs. Finally, these results enable us to prove that the complexity of recognizing planar median graphs is linear.