Authors
Citation
Ae. Kezdy et Hs. Snevily, ON EXTENSIONS OF A CONJECTURE OF GALLAI, J COMB TH B, 70(2), 1997, pp. 317-324
Citations number
6
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956
→ ACNP
Volume
70
Issue
2
Year of publication
1997
Pages
317 - 324
Database
ISI
SICI code
0095-8956(1997)70:2<317:OEOACO>2.0.ZU;2-M
Abstract
A graph G is k-critical if it has chromatic number k but every proper
subgraph of G has a (k - 1)-coloring. We prove the following result. I
f G is a k-critical graph of order n > R greater than or equal to 3, t
hen G contains fewer than n - 3k/5 + 2 complete subgraphs of Order k-1
. (C) 1997 Academic Press.