×

zbMATH — the first resource for mathematics

On the complexity of cover-incomparability graphs of posets. (English) Zbl 1172.05049
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)].

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.)
PDF BibTeX XML Cite
Full Text: DOI
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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.