A special case of Hadwiger's conjecture

Details A special case of Hadwiger's conjecture A special case of Hadwiger's conjecture

2005-01-05

arxiv.org/abs/math/0501073v1

Mathematics

Combinatorics

25 pages

Scientific paper

We investigate Hadwiger's conjecture for graphs with no stable set of size 3. Such a graph on at least 2t-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 always a minor in which the preimages of the vertices of $K_t$ are connected subgraphs of size one or two. We prove this strengthened version for graphs whose complement has an even number of vertices and fractional chromatic 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=|V(G)|$, a graph with no stable set of size 3 has a $K_{1/9 n^{4/5}}$ minor using only sets of size one or two as preimages of vertices.

Affiliated with

Also associated with

No associations

Rating

A special case of Hadwiger's conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A special case of Hadwiger's conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A special case of Hadwiger's conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-293012