Legal coloring of graphs |
| |
Authors: | N Linial |
| |
Institution: | (1) Institute of Mathematics and Computer Science, Hebrew University, 91 904 Jerusalem, Israel |
| |
Abstract: | The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981): Given a graphG=(V, E) and a real functionf:V→R which is a proposed vertex coloring. Decide whetherf is a proper vertex coloring ofG. The elementary steps are taken to be linear comparisons.
Lower bounds on the complexity of this problem are derived using the chromatic polynomial ofG. It is shown how geometric parameters of a space partition associated withG influence the complexity of this problem.
Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a
variety of computational problems. |
| |
Keywords: | 68 C 25 05 C 15 |
本文献已被 SpringerLink 等数据库收录! |
|