Packing six T-joins in plane graphs

DOI10.1016/J.JCTB.2015.09.002MaRDI QIDQ896004zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 11 December 2015

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

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)

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.

Recommendations

• scientific article; zbMATH DE number 927076
• On dyadic fractional packings of \(T\)-joins
• Two-trees optimal \(T\)-join and integral packing of \(T\)-cuts
• Third case of the cyclic coloring conjecture
• On packing \(T\)-cuts

Cites work

• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• Combinatorial optimization. Packing and covering
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edge-colouring eight-regular planar graphs
• Edge-colouring seven-regular planar graphs
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• Tutte's edge-colouring conjecture

Cited in

(10)

• Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees
• Packing odd T‐joins with at most two terminals
• scientific article; zbMATH DE number 927076 (Why is no real title available?)
• Graph edge coloring: a survey
• Circular coloring of signed bipartite planar graphs
• Edge-colouring eight-regular planar graphs
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem
• Walk-powers and homomorphism bounds of planar signed graphs
• A survey on flows in graphs and matroids

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)