The relationship between the threshold dimension of split graphs and various dimensional parameters (Q803177)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The relationship between the threshold dimension of split graphs and various dimensional parameters |
scientific article |
Statements
The relationship between the threshold dimension of split graphs and various dimensional parameters (English)
0 references
1991
0 references
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\).
0 references
boxicity
0 references
threshold dimension
0 references