Packing six T-joins in plane graphs

DOI10.1016/J.JCTB.2015.09.002zbMATH Open1327.05075DBLPjournals/jct/DvorakKK16arXiv1009.5912OpenAlexW2104251191WikidataQ57601321 ScholiaQ57601321MaRDI QIDQ896004FDOQ896004

Zdeněk Dvořák, Ken-ichi Kawarabayashi, Daniel Král'

Publication date: 11 December 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Let G be a plane graph and T an even subset of its vertices. It has been conjectured that if all T-cuts of G have the same parity and the size of every T-cut is at least k, then G contains k edge-disjoint T-joins. The case k=3 is equivalent to the Four Color Theorem, and the cases k=4, which was conjectured by Seymour, and k=5 were proved by Guenin. We settle the next open case k=6.

Full work available at URL: https://arxiv.org/abs/1009.5912

zbMATH Keywords

planar graphsedge coloring\(T\)-joins

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Tutte's edge-colouring conjecture
• Combinatorial optimization. Packing and covering
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Edge-colouring seven-regular planar graphs
• Edge-colouring eight-regular planar graphs

Cited In (10)

• Packing odd T‐joins with at most two terminals
• A survey on flows in graphs and matroids
• Circular coloring of signed bipartite planar graphs
• Edge-colouring eight-regular planar graphs
• Title not available (Why is that?)
• Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem
• 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
• Walk-powers and homomorphism bounds of planar signed graphs

This page was built for publication: Packing six \(T\)-joins in plane graphs

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