În teoria graficelor , un grafic de comparabilitate este un grafic neorientat care conectează perechi de elemente care sunt comparabile între ele într-o ordine parțială dată. De asemenea, se găsesc sub formă de grafice orientabile tranzitiv , grafice parțial ordonabile și grafice de izolare .
Graficele de comparabilitate sunt grafice perfecte .
Cele cographs sunt grafice de comparabilitate
Graficele care sunt de comparabilitate și al căror complement este, de asemenea, de comparabilitate sunt exact graficele permutărilor .
Graficele de comparabilitate pot fi recunoscute în timp liniar prin calcularea unei orientări. Mai multe probleme NP-complete în cazul general pot fi rezolvate în timp polinomial pentru aceste grafice cum ar fi colorarea , problema sandwich grafic sau chiar în timp liniar, cum ar fi problema maximă a clicii .