Algorithms and experiments on colouring squares of planar graphs

DOI10.1007/3-540-44867-5_2MaRDI QIDQ4426342zbMATH OpenFDO

Authors Maria I. Andreou, Sotiris E. Nikoletseas, P. G. Spirakis

Publication date 16 September 2003

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2647/26470015.htm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Communication networks in operations research (90B18)

Recommendations

• Heuristic for rapidly four-coloring large planar graphs
• New graph coloring algorithms
• A bound on the chromatic number of the square of a planar graph
• An O(N2) algorithm for coloring perfect planar graphs
• Coloring the square of a planar graph

Cited in

(3)

• An optimal square coloring of planar graphs
• Improved square coloring of planar graphs
• scientific article; zbMATH DE number 5305148 (Why is no real title available?)

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: Algorithms and experiments on colouring squares of planar graphs

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