Abstract
Let Ks,t* denote the graph obtained from the complete graph Ks+t by deleting the edges of some Kt-subgraph. The author proved earlier that for each fixed s and t>t0(s):= max{415s2+s,(240slog2s)8slog2s+1}, every graph with chromatic number s+t has a Ks,t* minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for t>C(slogs)3.
Original language | English (US) |
---|---|
Pages (from-to) | 377-386 |
Number of pages | 10 |
Journal | Journal of Graph Theory |
Volume | 75 |
Issue number | 4 |
DOIs | |
State | Published - Apr 2014 |
Keywords
- complete bipartite graphs
- graph coloring
- graph minors
ASJC Scopus subject areas
- Geometry and Topology