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

DOI10.1134/S1995080221040181MaRDI QIDQ2030141zbMATH OpenOpenAlexFDO

Authors Dmitrii V. Sirotkin, D. S. Malyshev

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

3-colourabilitycomputational complexityplanar graph

Mathematics Subject Classification ID

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

Recommendations

• On the complexity for constructing a 3-colouring for planar graphs with short facets
• An intractability result for the vertex 3-colourability problem
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Colouring vertices of triangle-free graphs

Cites work

• 3-colorability of pseudo-triangulations
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• On the complexity for constructing a 3-colouring for planar graphs with short facets
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

Cited in

(5)

• An intractability result for the vertex 3-colourability problem
• 3-colorability of pseudo-triangulations
• Coloring edges and vertices of graphs without short or long cycles
• On the complexity for constructing a 3-colouring for planar graphs with short facets
• Clustered 3-colouring graphs of bounded degree

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

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