Gallai's problem on Dirac's construction

✍ Scribed by D.A. Youngs

• Publisher: Elsevier Science
• Year: 1992
• Tongue: English
• Weight: 447 KB
• Volume: 101
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(92)90615-m

✦ Synopsis

It is thought that T. Gallai posed the following problem concerning a construction due to G.A. Dirac: suppose that a graph K consists of disjoint subgraphs G and Hand a set of edges joining them. If each of G, H, and K are colour critical graphs, under what circumstances is it then true that the join of G and His complete?

(That is to say, when is every vertex of G joined to every vertex of H?). In many cases the answer is affirmative, e.g. when G and H are both complete, as noted by Gallai. We present a small selection of graphs where the join is not complete.