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

From MaRDI portal
Revision as of 10:58, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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