21 votos

¿Por qué el coloreado de los bordes es menos interesante que el coloreado de los vértices?

Me preguntaba por qué hay (aparentemente) mucha más investigación dirigida a la coloración de los vértices que a la de los bordes. Prima facie parece que el coloreado de los bordes es algo tan "natural" como para investigarlo.

Se me ocurren algunas razones:

  1. La coloración del vértice se comporta bien bajo la supresión y contracción de los bordes.
  2. La coloración del vértice está estrechamente ligada al ciclo del matroide.
  3. La coloración de los bordes puede considerarse como coloración de vértices restringida a los gráficos lineales.
  4. Desde el teorema de Vizing (que el índice cromático de $G$ es o bien $ \Delta (G)$ o $ \Delta (G)+1$ ) el coloreado de los bordes se ha resuelto (asintóticamente).

¿Pero es realmente cierto que colorear los bordes es menos interesante que colorear los vértices?

27voto

crashmstr Puntos 15302

No es una respuesta, sino otra pregunta.

Cuando estaba en la escuela probé que el problema de los 4 colores es equivalente a la coloración de los bordes de los 3 colores del gráfico plano con el grado de cada vértice =3.

¿Es un teorema conocido? ¿Tiene un nombre?

20voto

Prasham Puntos 146

Hay un teorema que involucra la coloración de los bordes que es equivalente al teorema de los cuatro colores. La afirmación de que cada gráfico cúbico plano sin puente tiene una coloración de sus bordes que es equivalente al teorema de los cuatro colores. Un puente es un borde que cuando se borra aumenta el número de componentes conectados. Encontrar una prueba simple de este resultado sería un resultado importante porque la prueba del teorema de los cuatro colores es una prueba complicada. Hay un artículo disponible aquí en equivalentes del teorema de los cuatro colores

15voto

Darren Newton Puntos 835

No creo que el coloreado de los bordes se considere menos interesante. (Por supuesto I no lo creo, ya que es una de mis áreas de investigación...) Pero creo que mucha gente considera que los problemas de coloración de los bordes son algo más difíciles que los problemas de coloración de los vértices. El difunto Mike Albertson me dijo una vez que pensaba que estudiar la coloración de los vértices era como vagar por un bosque oscuro, y luego mirar hacia arriba y descubrir un pequeño claro... ¡Progreso! Pensó en estudiar la coloración de los bordes como si estuviera vagando en un bosque oscuro, y luego mirando hacia arriba y descubriendo que estaba en el mismo lugar donde empezó.

En cuanto al Teorema de Vizing... sí, los bordes de cualquier gráfico pueden ser coloreados usando $ \Delta $ o $ \Delta +1$ colores; los gráficos en la primera categoría son de la clase 1 y en la segunda de la clase 2. Dado un gráfico genérico, no es fácil decir en qué Clase cae el gráfico... incluso con mucha información sobre el gráfico (ejemplo: el gráfico es cúbico y de género 1).

Así que mi respuesta a tu pregunta es que se ha investigado menos sobre la coloración de los bordes porque es ligeramente más difícil que la coloración de los vértices.

5voto

pbh101 Puntos 2454

No sé si la coloración de los bordes es más o menos interesante que la coloración de los vértices, esto es probablemente algo que sólo podría ser resuelto por una encuesta. Las principales razones por las que la coloración de los bordes recibe menos atención que la coloración de los vértices, si tuviera que adivinar, ser el tercero y el cuarto que ofreces.

Tenga en cuenta que si $X$ es $k$ -gráfico regular, entonces el teorema de Vizing nos dice que su número cromático de borde es $k$ o $k+1$ . Si es así $k$ Entonces $X$ tiene una factorización de 1 podemos dividir sus bordes en $k$ y que se unan perfectamente en el borde. Hay una gran cantidad de literatura sobre problemas relacionados con las factorizaciones 1.

Se puede decir que la coloración del vértice es también más importante en la práctica, ya que surge en con importantes problemas de programación y asignación de registros. Aunque muchos de los somos matemáticos puros y puede que no sintamos la necesidad de considerar problemas prácticos, la influencia del "mundo real" en las matemáticas puras es, sin embargo, muy fuerte.

4voto

Zach Burlingame Puntos 7232

En realidad hacer creo que colorear los vértices es más interesante que colorear los bordes, aunque admito que es mi propio prejuicio personal. En lugar de centrarme en por qué la coloración de los bordes no es interesante, permítanme destacar por qué creo que la coloración de los vértices es interesante.

Conexiones con la topología . A lo largo de estas líneas está, por supuesto, el Teorema de los 4 colores , La conjetura del mapa de Heawood y El teorema de Grötzsch . Para los gráficos planares también hay una noción adecuada de dualidad de coloraciones a través de la dualidad flujo-coloración . La respuesta de Kristal es un ejemplo de la dualidad de flujo y color en acción. Es decir, basta con probar el teorema de los 4 colores para las triangulaciones planas. El dual de una triangulación planar es un gráfico planar cúbico. Por lo tanto, basta con mostrar que los gráficos planares cúbicos tienen 4 flujos, y es una especie de accidente que los 4 flujos de los gráficos cúbicos correspondan a coloraciones de 3 bordes.

Teoría de grafos estructurales . Tal vez el problema abierto más famoso de la teoría de grafos es La conjetura de Hadwiger que conecta la coloración de los vértices con las camarillas menores. Así que, un alto número cromático puede forzar alguna estructura, mientras que un alto número cromático de borde sólo fuerza un alto grado máximo.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X