Minors in ‐ Chromatic Graphs,II |
| |
| Authors: | A.V. Kostochka |
| |
| Affiliation: | 1. DEPARTMENT OF MATHEMATICS UNIVERSITY OF ILLINOIS, URBANA;2. SOBOLEV INSTITUTE OF MATHEMATICS, NOVOSIBIRSK, RUSSIA |
| |
| Abstract: | ![]()
Let  denote the graph obtained from the complete graph  by deleting the edges of some  ‐subgraph. The author proved earlier that for each fixed s and  , every graph with chromatic number  has a  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  . |
| |
| Keywords: | graph coloring graph minors complete bipartite graphs 05C15 05C83 |
|
|
