The relationship between the threshold dimension of split graphs and various dimensional parameters (Q803177)

The coboxicity of a graph G may be denoted by cob(G) and the threshold dimension by t(G). For fixed \(k\geq 3\), determining if cob(G)\(\geq k\) and t(G)\(\leq k\) are both NP-complete problems. The authors show that if G is a comparability graph, then one can determine if cob(G)\(\leq 2\) in polynomial time. This result shows that it is possible to determine if the interval dimension of a poset equals 2 in polynomial time. If the clique covering number of G is 2, they show that one can determine if t(G)\(\leq 2\) in polynomial time. Sufficient conditions on G are given for cob(G)\(\leq 2\) and for t(G)\(\leq 2\).