On the chromatic index of multigraphs and a conjecture of Seymour (I) (Q1084107): Difference between revisions

Let G be a multigraph with the set of vertices V and the set of edges E. We put \(E(S)=\{e|\) both ends of e belong to\(S\subseteq V\}\) and \(w(E(S))=\sum \{w_ e|\) \(e\in E(S)\}\). It is clear that the chromatic index of G is greater than or equal to the maximum vertex degree h of G. The second lower bound is given by \(\lceil k\rceil\), where \[ k=\max \{w(E(S))/((| S| -1)/2)|,\quad | S| \quad odd\quad and\quad | S| \neq 1\}. \] Seymour's conjecture says that the chromatic index of G is less than or equal to \(\max \{h+1,\lceil k\rceil \}\). This conjecture is verified for outerplanar graphs.