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
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
Gallai's problem
0 references
Dirac's construction
0 references
color-critical graphs
0 references