×

On k-critical n-chromatic graphs. (English) Zbl 0686.05022

Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 509-514 (1988).
[For the entire collection see Zbl 0673.00009.]
Let G be a finite simple undirected connected graph with the chromatic number \(\chi (G)=k\), i.e. \(\chi\) (G) is the smallest number of colours which can be assigned to the vertices of G such that adjacent vertices receive different colours. Then G is called a k-chromatic graph. A connected graph is called a (k,n)-graph if \(\chi (G)=n\) and \(\chi (G')=n- k\) for every graph \(G'\) arisen from G by deleting all vertices of a k- chromatic induced subgraph. In 1966 L. Lovász conjectured that, for \(2\leq k<n\), every (k,n)-graph contains a complete graph on n vertices as a subgraph. In this paper the conjecture is proved for the (k,n)-graphs with (k,n)\(\in \{(2,4),(2,5),(3,5),(3,6),(3,7)\}\).
Reviewer: U.Baumann

MSC:

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory

Citations:

Zbl 0673.00009