Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs

Name: Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs
Creator: Michael Stiebitz
Keywords: Connectivity, Coloring of graphs and hypergraphs, 0102 computer and information sciences, 0101 mathematics, number of connected components, 01 natural sciences, critical k-chromatic graphs, minor-vertices

Michael Stiebitz

Found an issue? Give us feedback

COMBINATORICAarrow_drop_down

COMBINATORICA

Article . 1982 . Peer-reviewed

License: Springer TDM

Data sources: Crossref

zbMATH Open

Article . 1982

Data sources: zbMATH Open

DBLP

Article

Data sources: DBLP

https://dx.doi.org/10.1007/bf0...

Article

Data sources: Microsoft Academic Graph

Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs

descriptionPublicationkeyboard_double_arrow_right Article 01 Sep 1982 English Publisher:Springer Science and Business Media LLCJournal:Combinatorica, volume 2, pages 315-323 (issn: 0209-9683, eissn: 1439-6912,

Copyright policy )

Authors: Michael Stiebitz;

doi: 10.1007/bf02579239

Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs

- Summary
- Subjects
- Related research
  (1)
- Metrics

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.

Keywords

Connectivity, Coloring of graphs and hypergraphs, number of connected components, critical k-chromatic graphs, minor-vertices

1 Research products, page 1 of 1

Problems in extremal graph theory and Euclidean Ramsey theory.
2019IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	15
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average