On the conjecture of hajós |
| |
Authors: | Paul Erdős Siemion Fajtlowicz |
| |
Institution: | (1) Mathematical Institute of the Hungarian Academy of Sciences, H-1053 Budapest, Hungary;(2) Department of Mathematics, University of Houston, 77004 Houston, Texas, U.S.A. |
| |
Abstract: | Hajós conjectured that everys-chromatic graph contains a subdivision ofK
s, the complete graph ons vertices. Catlin disproved this conjecture. We prove that almost all graphs are counter-examles in a very strong sense. |
| |
Keywords: | 05 C 15 60 C 05 |
本文献已被 SpringerLink 等数据库收录! |
|