## New answers tagged graph-minors

4
votes

Accepted

### $|G|/\alpha(G) \leq \eta(G)$ where $\eta(G)$ is the Hadwiger number

This weakening is still an open question, even in the very special case of graphs with $\alpha(G)=2$ (complements of triangle-free graphs). In other words, do all graphs with independence number two (...

Top 50 recent answers are included

#### Related Tags

graph-minors × 84graph-theory × 77

co.combinatorics × 38

graph-colorings × 10

reference-request × 9

hadwiger-conjecture × 8

infinite-combinatorics × 5

set-theory × 4

algorithms × 4

trees × 4

extremal-graph-theory × 3

topological-graph-theory × 3

planar-graphs × 3

linear-algebra × 2

matrices × 2

computational-complexity × 2

order-theory × 2

combinatorial-optimization × 2

hypergraph × 2

matroid-theory × 2

directed-graphs × 2

knot-link × 2

at.algebraic-topology × 1

rt.representation-theory × 1

lo.logic × 1