On the algorithmic complexity of coloring simple hypergraphs and steiner triple systems |
| |
Authors: | Kevin T. Phelps Vojtěch Rödl |
| |
Affiliation: | (1) Department of Mathematics, Georgia Institute of Technology, 30332 Atlanta, Georgia, USA;(2) FJFI ČVUT Department of Mathematics, Husova 5, Praha 1, Czechoslovakia |
| |
Abstract: | In this paper we establish that decidingt-colorability for a simplek-graph whent≧3,k≧3 is NP-complete. Next, we establish that if there is a polynomial time algorithm for finding the chromatic number of a Steiner Triple system then there exists a polynomial time “approximation” algorithm for the chromatic number of simple 3-graphs. Finally, we show that the existence of such an approximation algorithm would imply that P=NP. Dedicated to Paul Erdős on his seventieth birthday |
| |
Keywords: | 68 E 99 51 E 10, 05 B 05, 05 C 65 |
本文献已被 SpringerLink 等数据库收录! |
|