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, 2011 at 4:41
  • 1
    $\begingroup$ but the second question is ok (if horribly misspelled) $\endgroup$ Dec 19, 2011 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$ Dec 19, 2011 at 15:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.