A heuristic for the coloring of planar graphs

DOI10.1016/J.ENTCS.2020.10.008MaRDI QIDQ2133446OpenAlexWikidataFDO

Authors Cristina López-Ramírez, Ana E. De Ita-Varela, Jorge Eduardo Gutiérrez Gómez, Guillermo de Ita Luna

Publication date 29 April 2022

Full work available at URL https://doi.org/10.1016/j.entcs.2020.10.008

zbMATH Keywords

maximal independent setplanar graphsindependent paths3-coloring graph

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27)

Cites work

• 3-colouring AT-free graphs in polynomial time
• A Dual form of Kuratowski's Theorem
• A simple algorithm for 4-coloring 3-colorable planar graphs
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Chain hexagonal cacti: matchings and independent sets
• Coloring triangle-free graphs on surfaces
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Extremal Hosoya index and Merrifield-Simmons index of hexagonal spiders
• Maxima and minima of the Hosoya index and the Merrifield-Simmons index
• Planar graphs: Theory and algorithms
• The NP-completeness column: an ongoing guide
• The four-colour theorem

Cited in

(3)

• A search space ``cartography for guiding graph coloring heuristics
• An analysis of heuristics for graph planarization
• scientific article; zbMATH DE number 4134072 (Why is no real title available?)

This page was built for publication: A heuristic for the coloring of planar graphs

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