<p>I have 2 questions. </p>

<p>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 ?</p>

<p>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.   </p>

CC BY-SA 3.0
2011-12-19T04:41:47.070Z
To compare graph classes you can use http://graphclasses.org/ and its java application. Your first question is not of "research level".
didest
CC BY-SA 3.0
2011-12-19T04:59:13.270Z
but the second question is ok (if horribly misspelled)
Suresh Venkat
CC BY-SA 3.0
2011-12-19T15:33:50.813Z
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.
Michael Blondin
<cc.complexity-theory><graph-theory><co.combinatorics><graph-algorithms><sat>
On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT
Atsu Sai
# On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT

(Asked by: username_0 on 2011-12-19)

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.

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics, graph-algorithms, sat

> **Comments:**
> **username_1**: To compare graph classes you can use http://graphclasses.org/ and its java application. Your first question is not of "research level".  
> **username_2**: but the second question is ok (if horribly misspelled)  
> **username_3**: 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.  

---

## 0 answers

