On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation

DOI10.1002/jgt.20178zbMath1109.05039MaRDI QIDQ3418193

Carsten Thomassen

Publication date: 2 February 2007

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20178

zbMATH Keywords

Max-cut problem cubic planar graphs Chinese postman problem

Mathematics Subject Classification ID

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory