首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号