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
    0 references
    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
    0 references
    boxicity
    0 references
    threshold dimension
    0 references

    Identifiers