The chromatic index of nearly bipartite multigraphs (Q1076034): Difference between revisions

König's theorem states that if M is a bipartite multigraph with maximal valency \(\Delta\) (M) then the chromatic index \(\chi\) '(M) equals \(\Delta\) (M). A multigraph is called nearly bipartite if it is not bipartite but contains a vertex whose deletion yields a bipartite multigraph. The aim of this paper is to give a formula for \(\chi\) '(M) where M is nearly bipartite.