Cocomparability number

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

Cocomparability number --- число косравнимости.

The cocomparability number of a graph G, denoted ccp(G), is the smallest integer k such that G admits a k-CCPO (a k-cocomparability ordering). Note that ccp(G) = 1 if and only if \bar{G} (the complement of G) is a comparability graph.