The chromatic index of nearly bipartite multigraphs
type: Item
instance of: scholarly article
title: The chromatic index of nearly bipartite multigraphs
zbMATH Open document ID: 0593.05029
DOI: 10.1016/0095-8956(86)90065-1
author: Larry Eggan
author: Michael J. Plantholt
published in: Journal of Combinatorial Theory. Series B
publication date: 1986-01-01T00:00:00Z
review text: 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.
reviewed by: J.Sedláček
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3952797
zbMATH Keywords: bipartite multigraph
zbMATH Keywords: chromatic index
zbMATH Keywords: nearly bipartite
MaRDI profile type: Publication
full work available at URL: 0095-8956(86)90065-1
OpenAlex ID: W2021145615
cites work: On the edge-chromatic number of a graph
cites work: Q3342598
cites work: The chromatic index of graphs of even order with many edges
cites work: Q5604409
cites work: The NP-Completeness of Edge-Coloring
cites work: The Solution of a Timetabling Problem
cites work: Decomposition of Finite Graphs Into Forests
cites work: The chromatic index of graphs with large maximum degree
cites work: A generalized construction of chromatic index critical graphs from bipartite graphs
cites work: A Theorem on Coloring the Lines of a Network
description: scientific article; zbMATH DE number 3952797