On 3-colouring of graphs with short faces and bounded maximum vertex degree

DOI10.1134/S1995080221040181OpenAlexW3095781886MaRDI QIDQ2030141

Dmitriy S. Malyshev, Dmitrii V. Sirotkin

Publication date: 7 June 2021

Published in: Lobachevskii Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1995080221040181

zbMATH Keywords

computational complexityplanar graph3-colourability

Mathematics Subject Classification ID

Computer science (68-XX) Combinatorics (05-XX)

Cites Work

• Unnamed Item
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• 3-Colorability of Pseudo-Triangulations
• On the complexity for constructing a 3-colouring for planar graphs with short facets

This page was built for publication: On 3-colouring of graphs with short faces and bounded maximum vertex degree