I grafteori er en sammenlignbarhetsgraf en ikke-rettet graf som forbinder par av elementer som er sammenlignbare med hverandre i en gitt delrekkefølge . De finnes også som transittorienterbare grafer , delvis bestillbare grafer og inneslutningsgrafer .
Sammenlignbarhetsgrafer er perfekte grafer .
De cographs er sammenlignbar grafer
Grafene som er av sammenlignbarhet og hvis komplement også er av sammenlignbarhet, er nøyaktig grafene for permutasjoner .
Sammenlignbarhetsgrafer kan gjenkjennes i lineær tid ved å beregne en retning. Flere NP-komplette problemer i det generelle tilfellet kan løses i polynomial tid for disse grafene som farging , graf sandwichproblem eller til og med i lineær tid, som det maksimale klikkproblemet .