Talk:Comparability graph

Needs rework. The flow of the article does not help much to understand.

I donot know why this is identified to Ordal theory.

--Tangi-tamma (talk) 01:47, 4 April 2008 (UTC)[reply]

Incorrect characterization?

It seems to me that the property that every odd cycle has a triangular chord is not sufficient for a graph to be a comparability graph.

Consider e.g. the following graph (which is the complement of a 6-cycle):

  a - d
 /|   |\
c ----- f
 \|   |/
  e - b

Every cycle of odd length (i.e. length 5, since length 3 is trivial) has a triangular chord. However, the graph has no transitive orientation.

Yugu Thog (talk) 03:29, 17 October 2008 (UTC)[reply]

Gilmore and Hoffman (1964) state and prove this theorem, but just prior to it they define a "cycle" to be a walk that returns to the starting vertex and uses each edge at most once in each direction; they don't require the cycle to be simple. So in your case, e.g., a-d-f-c-e-b-d-a is an odd cycle with no triangular chords. I think probably a lot of subsequent authors quoted this result without paying attention to the strange definition. I'll see what can be done about clarifying this important point within the article. —David Eppstein (talk) 04:05, 17 October 2008 (UTC)[reply]

Incomparability graph

This concept is mentioned on the page about Dilworth's theorem, it links here, but is not mentioned. I have just added a definition for completeness.

As far as I see incomparability graphs are just the complements of comparability graphs. On the article page such complements are called "string graphs". String graphs have their own article page, but there is no mention of incomparability graphs there either. Furthermore the (broken) link "Fox, J.; Pach, J. (2009), String graphs and incomparability graphs." suggests that these are actually two different things. I am confused. Leen Droogendijk (talk) 14:33, 23 June 2012 (UTC)[reply]

Are comparability graphs chordal?

Are comparability graphs chordal? It seems to me that if you take any transitive directed graph and remove the directionality, the resulting graph must be chordal, but I may be wrong. --Doradus (talk) 15:51, 25 February 2010 (UTC)[reply]

No. Consider the comparability graph of the five-element partial order with the Hasse diagram shown below.

o   o
 \ /
  o
 / \
o   o

(That is, there are two minimal elements, two maximal elements, and one element in the middle between all of them.) Its comparability graph is a five-vertex wheel graph. There is no element whose neighborhood is a clique, in contrast to chordal graphs which can always be reduced to a smaller chordal graph by removing an element with a clique neighborhood. —David Eppstein (talk) 16:23, 25 February 2010 (UTC)[reply]

Oh, ok. Thanks very much. Let me see if I understand by labeling your vertices:

Now, 1-2-3-4 forms a cycle in the comparability graph, and that cycle has no chord. Is that right? --Doradus (talk) 06:57, 1 March 2010 (UTC)[reply]

Yes. —David Eppstein (talk) 07:05, 1 March 2010 (UTC)[reply]

Partial order is already transitive?

"That is, for a partially ordered set, take the directed acyclic graph, apply transitive closure, and remove orientation."

Why do I need to apply transitive closure, I though the partial order over the set is already transitive by definition? — Preceding unsigned comment added by 193.175.238.249 (talk) 10:55, 3 January 2022 (UTC)[reply]

Here here. I think the author means to start with the Hasse diagram? DavidRideout (talk) 16:51, 2 December 2022 (UTC)[reply]

Generalized cycle

What is a generalized cycle?? DavidRideout (talk) 16:54, 2 December 2022 (UTC)[reply]

It's clearly defined, in the article, two lines down from where it is first used. —David Eppstein (talk) 16:59, 2 December 2022 (UTC)[reply]

Citation or proof for equivalence of testing transitive orientation and matrix multiplication

"However, the algorithm for doing so will assign orientations to the edges of any graph, so to complete the task of testing whether a graph is a comparability graph, one must test whether the resulting orientation is transitive, a problem provably equivalent in complexity to matrix multiplication."

I would expect the proof or a citation for the claimed equivalence. It is easy enough to see that one can verify a transitive orientation by considering the squared adjacency matrix of the directed graph and testing for each positive entry that the same entry is 1 in the original adjacency matrix. However, I do not see why the reverse would hold and didn't find it in the literature. Paradoxonkatze (talk) 16:08, 9 November 2023 (UTC)[reply]

I think the equivalence between transitivity and matrix multiplication is in Aho, Garey, and Ullman (1972), "The transitive reduction of a directed graph", credited to earlier works by Ian Munro and some Russian paper. But maybe that's only the forward direction (you can compute transitive closures by matrix multiplying). In the other direction, computing the transitive closure of a two-level DAG is exactly the same as multiplying matrices over the Boolean semiring (not real numbers). So testing whether an orientation is transitive can easily be converted into testing whether a matrix product of this type has been computed correctly. —David Eppstein (talk) 16:33, 9 November 2023 (UTC)[reply]