Gallai's problem on Dirac's construction
type: Item
instance of: scholarly article
title: Gallai's problem on Dirac's construction
zbMATH Open document ID: 0766.05031
DOI: 10.1016/0012-365X(92)90615-M
author: D. A. Youngs
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: 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\).
reviewed by: Arthur T. White
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 89915
zbMATH Keywords: Gallai's problem
zbMATH Keywords: Dirac's construction
zbMATH Keywords: color-critical graphs
MaRDI profile type: Publication
cites work: Q5668821
cites work: Hajos' graph-coloring conjecture: Variations and counterexamples
cites work: Q5545303
cites work: Small graphs with chromatic number 5: A computer search
cites work: A Theorem on n-Coloring the Points of a Linear Graph
cites work: Balanced graphs and noncovering graphs
cites work: Nombre chromatique et plus longs chemins d'un graphe
cites work: Q3035305
cites work: On Colouring Partial Joins of a Complete Graph and a Cycle
full work available at URL: 0012-365x(92)90615-m
OpenAlex ID: W1971477663
description: scientific article; zbMATH DE number 89915