En la teoría de grafos, un gráfico de coincidencia es un gráfico que se puede dibujar en un plano de tal manera que todos sus bordes son segmentos de línea de longitud uno y los bordes no se cruzan. Por lo tanto, este gráfico tiene una incrustación en el plano tanto como gráfico de unidad de distancia como gráfico plano . Hablando de manera informal, un gráfico de coincidencias se puede diseñar mediante coincidencias que no se cruzan en una superficie plana , de ahí el nombre [1] .
Gran parte de la investigación sobre gráficos de fósforos se refiere a gráficos regulares en los que cada vértice tiene el mismo número de vecinos. Este número se llama el grado de la gráfica.
Se sabe que hay gráficos de coincidencia de todos los grados hasta el cuarto. Los gráficos completos con uno, dos y tres vértices (un solo vértice, una arista y un triángulo) son gráficos de fósforos, 0, 1 y 2 regulares, respectivamente. El gráfico más pequeño de 3 cerillas regulares está formado por dos copias de rombos ubicados de modo que los vértices correspondientes estén a la unidad de distancia. Su doble portada bipartita es la gráfica de un prisma octogonal con intersecciones [1] .
En 1986, Heiko Harbort presentó al Conde, que recibió su nombre: Conde de Harbort . Con 104 aristas y 52 vértices, este gráfico es el ejemplo más pequeño conocido de un gráfico de 4 coincidencias regulares [2] . El gráfico es rígido [3] .
Es imposible que un gráfico de coincidencia normal tenga un grado superior a cuatro [4] .
Como muestran Kurtz y Mazukolo [5] , el gráfico de cerillas libre de triángulos regulares más pequeño de 3 (circunferencia ≥ 4) tiene 20 vértices. Además, presentaron el ejemplo más pequeño conocido de un gráfico de 3 cerillas regulares con circunferencia 5 (180 vértices).
Verificar si un gráfico plano no dirigido dado se puede representar como un gráfico de cerillas es un problema NP-difícil [6] [7]
El número de gráficos de coincidencia diferentes (hasta el isomorfismo) se conoce hasta diez aristas [8] [9] :
1, 1 , 3 , 5 , 12 , 28 , 74 , 207, 633, 2008, …