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

DOI10.1016/j.entcs.2020.10.007OpenAlexW3110101364WikidataQ113317262 ScholiaQ113317262MaRDI QIDQ2133444

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

planar graphsvertex coloringmaximal independent setwheel graphspolyhedral wheel graphs

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27)

Cites Work

• Unnamed Item
• Planar graphs: Theory and algorithms
• The four-colour theorem
• A sufficient condition for planar graphs to be 3-colorable
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
• 3-Colouring AT-Free Graphs in Polynomial Time
• The NP-completeness column: an ongoing guide