Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Comparability graph

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order. For any strict partially ordered set (S,

Official source

https://en.wikipedia.org/wiki/Comparability_graph

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (3)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, disc ...

MATH-602: Inference on graphs

The class covers topics related to statistical inference and algorithms on graphs: basic random graphs concepts, thresholds, subgraph containment (planted clique), connectivity, broadcasting on trees, stochastic block models and perceptron models. Requirem ...

AR-301(ac): Studio BA5 (Bosshard et Vaquer)

The term sauvegarde is approached holistically from the side of care with the will to assist, protect, and therefore save. Design proposals grow out of the will to understand, looking for an overall critical view on the preexisting; built structure as well ...

Related lectures (7)

Public Administration and Economic Measurement

Explores the impact of economic measurement choices on data visibility and governance, emphasizing the importance of defining categories for understanding and policymaking.

Partial Ordering: Relations, Sequences, Summation

Explores partial orderings, divisibility relations, lattices, lexicographic ordering, comparability, and total orderings.

Equivalence Relations and Partial Orderings

Introduces equivalence relations, partitions, partial orderings, and total ordering concepts with examples and definitions.

Related publications (14)

Graph-based approximate message passing iterations

Raphaël Jean Berthier

Approximate message passing (AMP) algorithms have become an important element of high-dimensional statistical inference, mostly due to their adaptability and concentration properties, the state evolution (SE) equations. This is demonstrated by the growing ...

Oxford University Press2023

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...

CAMBRIDGE UNIV PRESS2020

Official source

https://en.wikipedia.org/wiki/Comparability_graph

About this result

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related courses (3)

CS-101: Advanced information, computation, communication I

MATH-602: Inference on graphs

AR-301(ac): Studio BA5 (Bosshard et Vaquer)

Related lectures (7)

Public Administration and Economic Measurement

Explores the impact of economic measurement choices on data visibility and governance, emphasizing the importance of defining categories for understanding and policymaking.

Partial Ordering: Relations, Sequences, Summation

Explores partial orderings, divisibility relations, lattices, lexicographic ordering, comparability, and total orderings.

Equivalence Relations and Partial Orderings

Introduces equivalence relations, partitions, partial orderings, and total ordering concepts with examples and definitions.

Related publications (14)

Graph-based approximate message passing iterations

Raphaël Jean Berthier

Oxford University Press2023

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

EPFL2023

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

CAMBRIDGE UNIV PRESS2020

Related concepts (22)

Order dimension

In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. first studied order dimension; for a more detailed treatment of this subject than provided here, see . The dimension of a poset P is the least integer t for which there exists a family of linear extensions of P so that, for every x and y in P, x precedes y in P if and only if it precedes y in all of the linear extensions.

Perfect graph theorem

In graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs. A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph.

Split graph

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by . A split graph may have more than one partition into a clique and an independent set; for instance, the path a–b–c is a split graph, the vertices of which can be partitioned in three different ways: the clique {a, b} and the independent set {c} the clique {b, c} and the independent set {a} the clique {b} and the independent set {a, c} Split graphs can be characterized in terms of their forbidden induced subgraphs: a graph is split if and only if no induced subgraph is a cycle on four or five vertices, or a pair of disjoint edges (the complement of a 4-cycle).

Related concepts (22)

Order dimension

Perfect graph theorem

Split graph