Paper Info
Title
Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
Abstract
Tibor Gallai made the following conjecture. LetG be ak-chromatic colour-critical graph. LetL denote the set of those vertices ofG having valencyk−1 and letH be the rest ofV(G). Then the number of components induced byL is not less than the number of components induced byH, providedL ≠ 0. We prove this conjecture in a slightly generalized form.
Year
DOI
Venue
1982
10.1007/BF02579239
Combinatorica
Keywords
Field
DocType
05 C 15, 05 C 40
Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Conjecture,Mathematics
Journal
Volume
Issue
ISSN
2
3
1439-6912
Citations 
PageRank 
References 
13
2.24
0
Authors
1
Name
Order
Citations
PageRank
Michael Stiebitz120730.08