Building a maximal independent set for the vertex-coloring problem on planar graphs

DOI10.1016/J.ENTCS.2020.10.007MaRDI QIDQ2133444zbMATH OpenOpenAlexWikidataFDO

Authors Cristina López-Ramírez, 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.007

zbMATH Keywords

maximal independent setplanar graphspolyhedral wheel graphsvertex coloringwheel graphs

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27)

Cites work

• 3-colouring AT-free graphs in polynomial time
• A sufficient condition for planar graphs to be 3-colorable
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• Coloring triangle-free graphs on surfaces
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Planar graphs: Theory and algorithms
• The four-colour theorem
• The NP-completeness column: an ongoing guide

Cited in

(3)

• scientific article; zbMATH DE number 1830756 (Why is no real title available?)
• The maximal f-dependent set problem for planar graphs is in NC
• The maximal \(f\)-dependent set problem for planar graphs is in NC

This page was built for publication: Building a maximal independent set for the vertex-coloring problem on planar graphs

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