0
$\begingroup$

I have 2 questions.

Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph which is is in Comparability Class but is not in Permutation Class ?

Secondly, There are several fast algorithm for vertex coloring of permutaion graph like poly time algorithms using dynamic way or NC parralel algorithms. Can we solve vertex colroing via converting instances of coloring to instances of 2-SAT? I think this solution is plausible, because any permutaion can be represented by several transpositions and we may be able to construct clause whose length is 2 using such transpositions.

$\endgroup$
3
  • 3
    $\begingroup$ To compare graph classes you can use graphclasses.org and its java application. Your first question is not of "research level". $\endgroup$ – didest Dec 19 '11 at 4:41
  • 1
    $\begingroup$ but the second question is ok (if horribly misspelled) $\endgroup$ – Suresh Venkat Dec 19 '11 at 4:59
  • 2
    $\begingroup$ You're basically asking whether vertex coloring for permutation graphs is in NL. Is a direct reduction to 2-SAT necessary? It might be easier to solve it with an NL machine, even though I barely know what a permutation graph is. $\endgroup$ – Michael Blondin Dec 19 '11 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.