Journal article
A special case of Hadwiger's conjecture
Journal of combinatorial theory. Series B, v 97(6), pp 1056-1073
01 Nov 2007
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We investigate Hadwiger's conjecture for graphs with no stable set of size 3. Such a graph on at least
2
t
−
1
vertices is not
t
−
1
colorable, so is conjectured to have a
K
t
minor. There is a strengthening of Hadwiger's conjecture in this case, which states that there is a
K
t
minor in which the preimage of each vertex of
K
t
is a single vertex or an edge. We prove this strengthened version for graphs with an even number of vertices and fractional clique covering number less than 3. We investigate several possible generalizations and obtain counterexamples for some and improved results from others. We also show that for sufficiently large
n, a graph on
n vertices with no stable set of size 3 has a
K
1
9
n
4
/
5
minor using only vertices and single edges as preimages of vertices.
Metrics
Details
- Title
- A special case of Hadwiger's conjecture
- Creators
- Jonah Blasiak - University of California, Berkeley
- Publication Details
- Journal of combinatorial theory. Series B, v 97(6), pp 1056-1073
- Publisher
- Elsevier
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000250065400012
- Scopus ID
- 2-s2.0-34548380431
- Other Identifier
- 991021862387704721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
Source: SDGs in the Output
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Mathematics