Hola, lo que tienes que hacer es lo siquiente, primero para poder asegurar la integridad referencial debes utilizar tablas innodb asegurate que estes usando ese tipo de tablas y no myisam, segundo una vez que insertaz un producto debes tomar ese id que se ha generado puedes hacerlo con una consulta sql algo como
SELECT MAX(id) FROM tu tabla o si estas utilizando php, con la instruccion mysql_insert_id() obtienes el identificador del ultimo registro insertado despues de hacer un insert, despues haces lo mismo con la categoria, y finalmente asignas esos dos valores en la tabla relacion. Espero que sirva.
Saludos
