En la teoría de grafos , una rama de las matemáticas, un bosque lineal es una especie de bosque formado a partir de la unión disjunta de gráficos de caminos . Es un gráfico no dirigido sin ciclos en el que cada vértice tiene un grado como máximo dos. Los bosques lineales son lo mismo que los bosques sin garras . Son los gráficos cuyo invariante gráfico de Colin de Verdière es como máximo 1. [1]
La arboricidad lineal de un gráfico es el número mínimo de bosques lineales en los que se puede dividir el gráfico. Para una gráfica de grado máximo, la arboricidad lineal es siempre al menos , y se conjetura que siempre es como mucho . [2]
Una coloración lineal de un gráfico es una coloración de gráfico adecuada en la que el subgráfico inducido formado por cada dos colores es un bosque lineal. El número cromático lineal de un gráfico es el menor número de colores utilizados por cualquier colorante lineal. El número cromático lineal es como máximo proporcional a, y existen gráficos para los que es al menos proporcional a esta cantidad. [3]
Referencias
- ^ van der Holst, Hein; Lovász, László ; Schrijver, Alexander (1999), "El parámetro gráfico de Colin de Verdière", Teoría de grafos y biología combinatoria (Balatonlelle, 1996) , Bolyai Soc. Matemáticas. Stud., 7 , Budapest: János Bolyai Math. Soc., Págs. 29–85.
- ^ Alon, N. (1988), "The linear arboricity of graphs", Israel Journal of Mathematics , 62 (3): 311–325, CiteSeerX 10.1.1.163.1965 , doi : 10.1007 / BF02783300 , MR 0955135.
- ^ Yuster, Raphael (1998), "Coloración lineal de gráficos", Matemáticas discretas , 185 (1-3): 293-297, doi : 10.1016 / S0012-365X (97) 00209-4 , MR 1614290.