Stretcher

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

Stretcher --- носилки.

A stretcher is a graph whose edge set may be partitioned into two triangles and three vertex-disjoint chordless paths, each with endpoints in both triangles

In a graph with no odd hole, every induced stretcher has three vertex-disjoint chordless paths of the same parity; therefore, a stretcher is called odd or even depending on the parity of the paths (odd or, respectively, even).