Coloración centrada

En teoría de grafos , una coloración centrada es un tipo de coloración de grafos relacionada con la profundidad del árbol . El número mínimo de colores en una coloración centrada de un grafo es igual a la profundidad del árbol del grafo . Una variante parametrizada, una${\displaystyle q}$La coloración centrada proporciona una forma de cubrir grafos con un pequeño número de subgrafos de profundidad de árbol como máximo${\displaystyle q}$y se puede utilizar en algoritmos para isomorfismo de subgrafos y problemas relacionados. El número de colores necesarios para un${\displaystyle q}$La coloración centrada está acotada en función de${\displaystyle q}$en las gráficas de expansión acotada .

Una coloración centrada es una coloración de grafos, una asignación de colores a los vértices de un grafo dado, con la siguiente propiedad: cada subgrafo conexo (o equivalentemente cada subgrafo inducido conexo ) tiene al menos un vértice cuyo color es único: ningún otro vértice en el mismo subgrafo tiene el mismo color. ^{[ 1 ]}

A${\displaystyle q}$La coloración centrada es una coloración centrada con la propiedad más débil de que cada subgrafo conexo (o equivalentemente cada subgrafo inducido conexo ) tiene al menos${\displaystyle q}$colores, o tiene al menos un vértice cuyo color es único. ^{[ 2 ]} Para${\displaystyle q=2}$Esta es una coloración de grafos ordinaria: cada arista, y por lo tanto cada subgrafo conectado más grande, debe tener al menos dos colores. ^{[ 3 ]} Para${\displaystyle q=3}$a${\displaystyle q}$La coloración centrada es lo mismo que una coloración estrella : cada subgrafo con solo dos colores debe ser una unión disjunta de estrellas , centrada en los vértices de color único de cada componente. Para${\displaystyle q>n}$, dónde${\displaystyle n}$es el número de vértices en el grafo, es imposible tener${\displaystyle q}$colores y un${\displaystyle q}$La coloración centrada es lo mismo que una coloración centrada sin el parámetro. Más concretamente, siempre que${\displaystyle q}$es al menos igual a la profundidad del árbol${\displaystyle t}$de un gráfico dado, el número de colores en un${\displaystyle q}$La coloración centrada también es al menos igual a${\displaystyle t}$. ^{[ 4 ]}

El número mínimo de colores en una coloración centrada de un gráfico dado${\displaystyle G}$iguala a su profundidad de árbol , la altura mínima de un bosque enraizado${\displaystyle F}$en el mismo conjunto de vértices que${\displaystyle G}$de tal manera que cada borde en${\displaystyle G}$conecta un par ancestro-descendiente en${\displaystyle F}$. En una dirección, si${\displaystyle F}$es un bosque con esta propiedad, se puede obtener una coloración centrada con un número de colores igual a su altura agrupando los vértices de${\displaystyle F}$por distancia desde las raíces de sus árboles y usando un color para cada grupo. En la otra dirección, desde una coloración centrada de${\displaystyle G}$, uno puede obtener un bosque${\displaystyle F}$con las propiedades deseadas, eligiendo una raíz de árbol con un color único en cada componente de${\displaystyle G}$, con los hijos de cada raíz construidos recursivamente a partir de los subgrafos conectados obtenidos al eliminar la raíz de${\displaystyle G}$. ^{[ 5 ]}

En un${\displaystyle q}$coloración centrada, cada subconjunto de${\displaystyle k}$colores donde${\displaystyle k<q}$induce un subgrafo en el que la coloración es una coloración centrada. Por lo tanto, este subgrafo inducido tiene una profundidad de árbol como máximo${\displaystyle k}$. ^{[ 6 ]} Al elegir todos los subconjuntos de un número determinado de colores, cualquier grafo con un${\displaystyle q}$La coloración centrada en puede ser cubierta por grafos de profundidad de árbol limitada. En particular, si se desea buscar copias de un grafo${\displaystyle H}$con${\displaystyle h}$vértices como subgrafos de un grafo mayor${\displaystyle G}$(el problema del isomorfismo de subgrafos) y${\displaystyle G}$tiene un${\displaystyle (h+1)}$-coloración centrada con${\displaystyle k}$colores, luego cualquier copia de${\displaystyle H}$puede utilizar como máximo${\displaystyle h}$de los colores. Se pueden encontrar todas las copias de${\displaystyle H}$en los subgrafos de${\displaystyle G}$inducido por todos${\displaystyle h}$-tuplas de colores. Esta idea reduce el problema del isomorfismo de subgrafos a${\displaystyle O(k^{h})}$subproblemas, cada uno de los cuales puede resolverse rápidamente debido a su baja profundidad de árbol. La misma idea se aplica también a comprobar si${\displaystyle G}$modela cualquier fórmula de primer orden en la lógica de los gráficos que utiliza únicamente${\displaystyle h}$variables. ^{[ 7 ]}

Para que este método sea eficiente, es importante que el número de colores en un${\displaystyle q}$La coloración centrada debe ser pequeña. Para gráficos de expansión acotada , este número está acotado por un polinomio de${\displaystyle q}$cuyo exponente (grande) depende de la familia. ^{[ 8 ]} De manera más general, para grafos en una familia de grafos no densa en ninguna parte , este número es${\displaystyle o(|V(G)|).}$Sin embargo, para las clases de grafos que son densas en algún lugar (es decir, no densas en ningún lugar), no es posible tal límite. ^{[ 9 ]} Para grafos de grado limitado, el número de colores es${\displaystyle O(q)}$, para grafos planares es${\displaystyle O(q^{3}\log q)}$y para grafos con un menor topológico prohibido es polinomial en${\displaystyle q}$. ^{[ 10 ]}

• Dębski, Michał; Felsner, Stefan; Micek, Piotr; Schröder, Felix (2021), "Improved bounds for centered colorings", Advances in Combinatorics 8, arXiv : 1907.04586 , doi : 10.19086/aic.27351 , MR 4309118 
• Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol.  28, Springer, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR 2920058