Guthrie's problem: new equivalences and rapid reductions

DOI10.1016/0304-3975(95)00126-3MaRDI QIDQ672855zbMATH OpenOpenAlexFDO

Authors Artur Czumaj, A. Gibbons

Publication date 28 February 1997

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(95)00126-3

zbMATH Keywords

3-edge colouring of pairs of treesfour-colour problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Further reductions for the \(k(GV)\)-problem
• scientific article; zbMATH DE number 4034376
• Publication:3027633
• scientific article; zbMATH DE number 3973172
• scientific article; zbMATH DE number 2070522
• A new proof of the Garsia-Wachs algorithm
• A new insight into Serre's reduction problem
• The Guderley problem revisited
• scientific article; zbMATH DE number 3016176
• A new approach to thek(GV)-problem

Cites work

• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 3724488 (Why is no real title available?)
• scientific article; zbMATH DE number 1256642 (Why is no real title available?)
• scientific article; zbMATH DE number 3241107 (Why is no real title available?)
• A Theorem on Planar Graphs
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• Every planar map is four colorable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Problems on pairs of trees and the four colour problem of planar graphs (extended abstract)
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs

Cited in

(8)

• scientific article; zbMATH DE number 140087 (Why is no real title available?)
• scientific article; zbMATH DE number 4134068 (Why is no real title available?)
• scientific article; zbMATH DE number 4033776 (Why is no real title available?)
• Rotation sequences and edge-colouring of binary tree pairs
• Problems on pairs of trees and the four colour problem of planar graphs (extended abstract)
• scientific article; zbMATH DE number 3987302 (Why is no real title available?)
• Toward a language theoretic proof of the four color theorem
• Map coloring and the vector cross product

This page was built for publication: Guthrie's problem: new equivalences and rapid reductions

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