Ks,t minors in (s + t) - Chromatic graphs, II

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)377-386
Number of pages10
JournalJournal of Graph Theory
Issue number4
StatePublished - Apr 2014


  • complete bipartite graphs
  • graph coloring
  • graph minors

ASJC Scopus subject areas

  • Geometry and Topology


Dive into the research topics of 'Ks,t minors in (s + t) - Chromatic graphs, II'. Together they form a unique fingerprint.

Cite this