Nearly bipartite graphs with large chromatic number |
| |
Authors: | Vojtěch Rödl |
| |
Institution: | (1) Dept. of Mathematics, FJFI ČVUT, 11000 Praha, 1 ČSSR |
| |
Abstract: | P. Erdős and A. Hajnal asked the following question. Does there exist a constant ε>0 with the following property: If every
subgraphH of a graphG can be made bipartite by the omission of at most ε|H| edges where |H| denotes the number of vertices ofH thenx(H) ≦ 3.
The aim of this note is to give a negative answer to this question and consider the analogous problem for hypergraphs. The
first was done also by L. Lovász who used a different construction. |
| |
Keywords: | 05 C 15 05 C 65 |
本文献已被 SpringerLink 等数据库收录! |
|