Gallai's problem on Dirac's construction (Q1197042)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Gallai's problem on Dirac's construction
scientific article

    Statements

    Gallai's problem on Dirac's construction (English)
    0 references
    0 references
    16 January 1993
    0 references
    Let a graph \(K\) consist of disjoint graphs \(G\) and \(H\) and a set of edges joining \(G\) and \(H\). If each of \(G\), \(H\), and \(K\) are color-critical, when is every vertex of \(G\) joined to every vertex of \(H\) (i.e. \(K=G+H)?\) This does occur, for example, if \(G\) and \(H\) are both complete. In this paper a small selection of such color-critical graphs \(G\), \(H\), and \(K\) is presented for which \(K\neq G+H\).
    0 references
    0 references
    Gallai's problem
    0 references
    Dirac's construction
    0 references
    color-critical graphs
    0 references
    0 references