Back to Search Start Over

IMPROVED BOUNDS FOR TOPOLOGICAL CLIQUES IN GRAPHS OF LARGE GIRTH.

Authors :
Kühn, Daniela
Osthus, Deryk
Source :
SIAM Journal on Discrete Mathematics. 2006, Vol. 20 Issue 1, p62-78. 17p. 7 Diagrams.
Publication Year :
2006

Abstract

We prove that every graph of minimum degree at least r and girth at least 27 contains a subdivision of Kr+1. This implies that the conjecture of Hajós, that every graph of chromatic number at least r contains a subdivision of Kr, is true for graphs of girth at least 27. This conjecture is known to be false in general. [ABSTRACT FROM AUTHOR]

Subjects

Subjects :
*GRAPHIC methods
*POLYNOMIALS
*LOGICAL prediction
*TOPOLOGY
*SET theory

Details

Language :
English
ISSN :
08954801
Volume :
20
Issue :
1
Database :
Academic Search Index
Journal :
SIAM Journal on Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
25290883
Full Text :
https://doi.org/10.1137/040617765
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details