On extensions of a conjecture of Gallai
type: Item
instance of: scholarly article
title: On extensions of a conjecture of Gallai
zbMATH Open document ID: 0880.05041
author: André E. Kézdy
author: Hunter Snevily
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-08-12T00:00:00Z
review text: The authors show that in a \(k\)-critical graph \((k\geq 3)\) with more than \(k\) vertices, there exists an edge that is in fewer than \(2k/5\) cliques of size \(k-1\). They use this result to prove that if \(G\) is a \(k\)-critical graph of order \(n>k\geq 3\), then \(G\) contains fewer than \(n-3k/5+2\) complete subgraphs of order \(k-1\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1042503
zbMATH Keywords: conjecture of Gallai
zbMATH Keywords: \(k\)-critical graph
zbMATH Keywords: complete subgraphs
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
full work available at URL: jctb.1997.1764
OpenAlex ID: W2034416887
cites work: On a conjecture of Gallai concerning complete subgraphs of \(k\)-critical graphs
cites work: 25 pretty graph colouring problems
cites work: On constructive methods in the theory of colour-critical graphs
cites work: Subgraphs of colour-critical graphs
cites work: Q4848779
cites work: On complete subgraphs of color-critical graphs
DOI: 10.1006/JCTB.1997.1764
Recommended article: A note on a conjecture of Gallai
Recommended article: Extended Gallai's theorem
Recommended article: On a conjecture of Gackstatter and Laine
Recommended article: On a generalization of a conjecture of Grosswald
Recommended article: On a generalization of the Gallai-Sylvester theorem
Recommended article: On a conjecture of Gentner and Rautenbach
Recommended article: Extensions of the Multiplicity conjecture
Recommended article: Galois extensions and a conjecture of Ogg
Recommended article: Q4873815
Recommended article: On a conjecture of Gottlieb
description: scientific article; zbMATH DE number 1042503