Optimal edge-colourings for a class of planar multigraphs

DOI10.1007/S004930100002MaRDI QIDQ5955208zbMATH OpenOpenAlexFDO

Authors Odile Marcotte

Publication date 13 February 2002

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930100002

zbMATH Keywords

optimal edge-coloringsplanar multigraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Programming involving graphs or networks (90C35)

Review text

The author determines the chromatic index of multigraphs containing no minors isomorphic either to \(K_{3,3}\) or \({K_5}-e\) (this latter means \(K_5\) without one of its edges). The answer (the maximum of the maximum valency and a function on the odd subset of the vertices) partially verifies a conjecture of \textit{P. D. Seymour} [J. Comb. Theory, Ser. B 31, 82--94 (1981; Zbl 0471.05031)] and is a generalization of a result of \textit{P. D. Seymour} [Combinatorica 10, No. 4, 379--392 (1990; Zbl 0721.05023)] for series-parallel graphs.

Recommendations

• scientific article; zbMATH DE number 4195987
• scientific article; zbMATH DE number 4195986
• On the chromatic index of multigraphs and a conjecture of Seymour (I)
• The chromatic index of multigraphs that are nearly full
• A note concerning the chromatic index of multigraphs

Cited in

(8)

• On the chromatic index of multigraphs and a conjecture of Seymour (I)
• Graph edge coloring: a survey
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees
• scientific article; zbMATH DE number 4195986 (Why is no real title available?)
• scientific article; zbMATH DE number 4195987 (Why is no real title available?)
• A characterization of multigraphs reaching Goldberg's bound of chromatic index
• Matching polytopes, Gorensteinness, and the integer decomposition property

This page was built for publication: Optimal edge-colourings for a class of planar multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5955208)