On the complexity of cover-incomparability graphs of posets. (English) Zbl 1172.05049

Maxová, Jana; Pavlíková, Pavla; Turzík, Daniel

Order 26, No. 3, 229-236 (2009).

The cover-incomparability graph (or C-I graph) \(G\) of a poset \(P=(V,\leq)\) has vertex set \(V\), and two vertices \(x\) and \(y\) are adjacent in \(G\) if \(x\) covers \(y\) in \(P\), or \(y\) covers \(x\) in \(P\), or \(x\) and \(y\) are incomparable in \(P\), see B. Brešar, M. Changat, S. Klavžar, M. Kovše, J. Mathews, and A. Mathews [Order 25, No. 4, 335–347 (2008; Zbl 1219.06004)]. The recognition problem for C-I graphs is NP-complete, but the induced subgraphs of C-I graphs form exactly the class of cocomparability graphs, and can therefore be recognised in linear time, see R. M. McConnell and J. P. Spinrad [Discrete Math. 201, No. 1-3, 189–241 (1999; Zbl 0933.05146)].

Reviewer: Haiko Müller (Leeds)

MSC:

05C75	Structural characterization of families of graphs
05C62	Graph representations (geometric and intersection representations, etc.)
06A07	Combinatorics of partially ordered sets
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

poset; graph; transitive orientation; cocomparability graph; NP-complete

References:

[1]	Brandstädt, A., Le, V.B., Spinard, J.: Graph Classes. SIAM, Philadelphia (1999)
[2]	Brešar, B., Changat, M., Klavžar, S., Kovše, M., Mathews, J., Mathews, A.: Cover-incomparability graphs of posets. Order 25, 335–347 (2008) · Zbl 1219.06004 · doi:10.1007/s11083-008-9097-1
[3]	Brigtwell, G.: On the complexity of diagram testing. Order 10, 297–303 (1993) · Zbl 0808.06003 · doi:10.1007/BF01108825
[4]	Gallai, T.: Transitiv orientierbare graphen. Acta Math. Acad. Sci. Hung. 18, 25–66 (1967) · Zbl 0153.26002 · doi:10.1007/BF02020961
[5]	Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completness. Freeman, New York (1979) · Zbl 0411.68039
[6]	Golumbic, M.: Algorithmic graph theory and perfect graphs, academic press, 2nd edn. Ann. Discrete Math. 57 (2004) · Zbl 1050.05002
[7]	Lovász, L.: Combinatorial Problems and Exercises. Akadémiai Kaidó, Budapest (1979) · Zbl 0439.05001
[8]	Nešetřil, J., Rödl,V.: Complexity of diagrams. Order 3, 321–330 (1987) · Zbl 0808.06004 · doi:10.1007/BF00340774
[9]	Nešetřil, J., Rödl, V.: More on the complexity of cover graphs. Comment. Math. Univ. Carol. 36, 269–278 (1995) · Zbl 0829.06002
[10]	Orlin, J.: Contentment in graph theory: covering graphs with cliques. Indag. Math. 39, 406–424 (1977) · Zbl 0374.05041
[11]	Rival, I.: The role of graphs in the theory of ordered sets and its applications. J. Symb. Log. 57, 269–271 (1992) · doi:10.2307/2275198
[12]	Trotter, W.T.: Graphs and partially ordered sets: recent results and new directions. Congr. Numer. 116, 253–278 (1996) · Zbl 0902.05038