Improved bounds for topological cliques in graphs of large girth

Daniela Kuhn; Deryk Osthus

doi:10.1137/040617765

Improved bounds for topological cliques in graphs of large girth

Daniela Kuhn, Deryk Osthus

Mathematics

Research output: Contribution to journal › Article

5 Citations (Scopus)

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 Hajos, that every graph of chromatic number at least r contains a subdivision of K-r, is true for graphs of girth at least 27. This conjecture is known to be false in general.

Original language	English
Pages (from-to)	62-78
Number of pages	17
Journal	SIAM Journal on Discrete Mathematics
Volume	20
DOIs	https://doi.org/10.1137/040617765
Publication status	Published - 1 Jan 2006

Keywords

Hajos conjecture
topological minors
girth
subdivisions

Access to Document

10.1137/040617765

Cite this

@article{93d96c41fbae497bb4632c411fd2aa91,

title = "Improved bounds for topological cliques in graphs of large girth",

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 Hajos, that every graph of chromatic number at least r contains a subdivision of K-r, is true for graphs of girth at least 27. This conjecture is known to be false in general.",

keywords = "Hajos conjecture, topological minors, girth, subdivisions",

author = "Daniela Kuhn and Deryk Osthus",

year = "2006",

month = jan,

day = "1",

doi = "10.1137/040617765",

language = "English",

volume = "20",

pages = "62--78",

journal = "SIAM Journal on Discrete Mathematics",

publisher = "Society for Industrial and Applied Mathematics Publications",

}

TY - JOUR

T1 - Improved bounds for topological cliques in graphs of large girth

AU - Kuhn, Daniela

AU - Osthus, Deryk

PY - 2006/1/1

Y1 - 2006/1/1

N2 - 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 Hajos, that every graph of chromatic number at least r contains a subdivision of K-r, is true for graphs of girth at least 27. This conjecture is known to be false in general.

AB - 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 Hajos, that every graph of chromatic number at least r contains a subdivision of K-r, is true for graphs of girth at least 27. This conjecture is known to be false in general.

KW - Hajos conjecture

KW - topological minors

KW - girth

KW - subdivisions

UR - http://www.scopus.com/inward/record.url?scp=33847611651&partnerID=8YFLogxK

U2 - 10.1137/040617765

DO - 10.1137/040617765

M3 - Article

VL - 20

SP - 62

EP - 78

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

ER -

Improved bounds for topological cliques in graphs of large girth

Abstract

Keywords

Access to Document

Fingerprint

Cite this