Rotation sequences and edge-colouring of binary tree pairs

DOI10.1016/J.TCS.2004.06.018MaRDI QIDQ703564zbMATH OpenOpenAlexFDO

Authors Paul Sant, A. Gibbons

Publication date 11 January 2005

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

Full work available at URL https://doi.org/10.1016/j.tcs.2004.06.018

zbMATH Keywords

RotationBinary treeFour-colour problemGraph coloring

Mathematics Subject Classification ID

Trees (05C05) Combinatorics in computer science (68R05) Coloring of graphs and hypergraphs (05C15)

Recommendations

• scientific article; zbMATH DE number 1929924
• Problems on pairs of trees and the four colour problem of planar graphs (extended abstract)
• Guthrie's problem: new equivalences and rapid reductions
• Every Planar Map is Four Colorable
• Toward a language theoretic proof of the four color theorem

Cites work

• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 1929924 (Why is no real title available?)
• scientific article; zbMATH DE number 1439421 (Why is no real title available?)
• A note on some tree similarity measures
• Every planar map is four colorable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Guthrie's problem: new equivalences and rapid reductions
• Rotation Distance, Triangulations, and Hyperbolic Geometry
• The four-colour theorem
• Twist–Rotation Transformations of Binary Trees and Arithmetic Expressions

Cited in

(8)

• Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order
• A Constant Amortized Time Algorithm for Generating Left-Child Sequences in Lexicographic Order
• A metric for rooted trees with unlabeled vertices based on nested parentheses
• On the rotation distance between binary trees
• Problems on pairs of trees and the four colour problem of planar graphs (extended abstract)
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• Refined upper bounds for right-arm rotation distances
• Toward a language theoretic proof of the four color theorem

This page was built for publication: Rotation sequences and edge-colouring of binary tree pairs

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