Problems on pairs of trees and the four colour problem of planar graphs

DOI10.1007/3-540-56939-1_64zbMath1418.68101OpenAlexW1591264896MaRDI QIDQ4630251

Alan M. Gibbons, Artur Czumaj

Publication date: 29 March 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_64

zbMATH Keywords

split graphHamiltonian cycleregular languageplanar graphdual graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Formal languages and automata (68Q45) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

Guthrie's problem: new equivalences and rapid reductions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
• A Theorem on Planar Graphs
• 2-Isomorphic Graphs

This page was built for publication: Problems on pairs of trees and the four colour problem of planar graphs