Three colorability characterized by shrinking of locally connected subgraphs into triangles

DOI10.1016/j.ipl.2018.02.016zbMath1476.05057OpenAlexW2793655049MaRDI QIDQ1708265

Martin Kochol

Publication date: 5 April 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.02.016

zbMATH Keywords

graph algorithms3-colorability(strongly) \(\Delta\)-reducible graph\(\Delta\)-reductionlocally-connected graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Further extensions of the Grötzsch theorem ⋮ Note on 3-choosability of planar graphs with maximum degree 4

Cites Work

• Unnamed Item
• Unnamed Item
• Colorability of planar graphs with isolated nontriangular faces
• Some simplified NP-complete graph problems
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• 3-coloring and 3-clique-ordering of locally connected graphs
• 3-coloring in time

This page was built for publication: Three colorability characterized by shrinking of locally connected subgraphs into triangles