An improved bound on the minimal number of edges in color-critical graphs
type: Item
instance of: scholarly article
title: An improved bound on the minimal number of edges in color-critical graphs
zbMATH Open document ID: 0885.05063
author: Michael Krivelevich
published in: The Electronic Journal of Combinatorics
publication date: 1998-02-18T00:00:00Z
full work available at URL: https://eudml.org/doc/119251
full work available at URL: v5i1r4.html
review text: Summary: It is proven that for \(k\geq 4\) and \(n>k\) every \(k\)-color-critical graph on \(n\) vertices has at least \(\left(\frac{k-1}{2}+\frac{k-3}{2(k^2-2k-1)}\right)n\) edges, thus improving a result of Gallai from 1963.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1119069
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1119069