Colouring series-parallel graphs

DOI10.1007/BF02128672zbMath0721.05023MaRDI QIDQ2640612

P. D. Seymour

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

chromatic indexvertex colouringcolouring algorithmseries-parallel graphedge colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (14)

Fractional and integral colourings ⋮ Partitioning series-parallel multigraphs into \(v^*\)-excluding edge covers ⋮ Unnamed Item ⋮ Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs ⋮ The Flow Index of Regular Class I Graphs ⋮ Approximate strong separation with application in fractional graph coloring and preemptive scheduling. ⋮ Approximating the chromatic index of multigraphs ⋮ Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees ⋮ On graphs with no induced subdivision of \(K_4\) ⋮ Graph edge coloring: a survey ⋮ Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs ⋮ The determination of the total chromatic number of series-parallel graphs with \((G) \geq 4\) ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ The entire coloring of series-parallel graphs

Cites Work

• Unnamed Item
• On the chromatic index of multigraphs and a conjecture of Seymour (I)
• Matroids and multicommodity flows
• The ellipsoid method and its consequences in combinatorial optimization
• Topology of series-parallel networks
• The NP-Completeness of Edge-Coloring
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Maximum matching and a polyhedron with 0,1-vertices
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: Colouring series-parallel graphs