Partición del grafo ' s los bordes en 3 grupos

Question

Deje $G = (V, E)$ ser un bipartito gráfico.

Demostrar que no es una partición del conjunto de aristas $E$ en 3 partes disjuntas:

$E = E1 ∪ E2 ∪ E3$, $E1 ∩ E2 = E2 ∩ E3 = E3 ∩ E1 = ∅$, de modo que para cada vértice $v$$G$, y para cada una de las $1 ≤ i ≤ 3$, el grado $deg_i(v)$ $v$ en el gráfico de $(V, E_i)$ satisface:

$\lfloor{\frac{deg(v)}{3}}\rfloor$ $≤ d_i(v) ≤$ $\lceil{\frac{deg(v)}{3}}\rceil$,

Donde $deg(v)$ es el grado de $v$$G$.

(Sugerencia: divida a los vértices para que tengan el máximo grado 3, y encontrar un borde adecuado para colorear por los 3 colores.)

Yo no entendía la indirecta , además , incluso si tiene un gráfico de máximo grado 3 , según Vizing puede tener cromática(índice de óptimo borde de color) de 4.

Voy a ser feliz si alguien me podría dar una mejor sugerencia, ya que estoy muy perdido. Cuando traté de resolver este ni siquiera he pensado acerca de borde para colorear...

Además, este resultado puede ser generalizado?

Answer 1

En general, si $G$ tiene el grado máximo $\Delta$, entonces la cromática índice de $G$ es $\Delta$ o $\Delta+1$. Para algunos gráficos especiales, como bipartita de los gráficos, la cromática índice siempre es $\Delta$.

El resultado se puede generalizar de la siguiente manera.

Deje $G=(V,E)$ ser un bipartito gráfico. Deje $k\geq1$ ser un número entero. A continuación, $E$ se puede dividir en $k$ partes $E_1,E_2,...,E_k$, de modo que $\lfloor\dfrac{deg(v)}{k}\rfloor\leq{d_i(v)}\leq\lceil\dfrac{deg(v)}{k}\rceil$ todos los $v\in{V}$, para todos los $i=1,...,k$.

Como en la pista, primero dividir cada vértice $v$ a $\lceil\dfrac{deg(v)}{k}\rceil$ vértices, donde $\lfloor\dfrac{deg(v)}{k}\rfloor$ de ellos tienen un grado $k$ y un vértice (si es necesario) de grado $n-\lfloor\dfrac{deg(v)}{k}\rfloor{k}$.

A continuación, el gráfico resultante $G'$ tiene el grado máximo $k$, por lo que la cromática índice de $G'$$k$, es decir, $E(G')$ es una unión de $k$ matchings $M_1,...,M_k$.

Identificar los puntos de división antes, obtenemos $E_1,...,E_k$, que es una partición de a $E$. Queda por comprobar que para cada $i$, $d_i(v)$ satisface la desigualdad para todos los $v\in{V}$.

Desde $M_i$ es una coincidencia, hay un borde en $M_i$ incidente con cada una de las $\lceil\dfrac{deg(v)}{k}\rceil$ vértices correspondientes a $v\in{G}$, obtenemos ${d_i(v)}\leq\lceil\dfrac{deg(v)}{k}\rceil$.

Entre los vértices en $G'$ correspondiente a $v$, $\lfloor\dfrac{deg(v)}{k}\rfloor$ de ellos tienen un grado $k$. Cada vértice debe incidente con un borde en $M_i$. Por lo tanto, $\lfloor\dfrac{deg(v)}{k}\rfloor\leq{d_i(v)}$.