Three colorability characterized by shrinking of locally connected subgraphs into triangles
type: Item
instance of: scholarly article
title: Three colorability characterized by shrinking of locally connected subgraphs into triangles
zbMATH Open document ID: 1476.05057
author: Martin Kochol
published in: Information Processing Letters
publication date: 2018-04-05T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6856065
zbMATH Keywords: locally-connected graph
zbMATH Keywords: 3-colorability
zbMATH Keywords: \(\Delta\)-reduction
zbMATH Keywords: (strongly) \(\Delta\)-reducible graph
zbMATH Keywords: graph algorithms
MaRDI profile type: Publication
full work available at URL: j.ipl.2018.02.016
OpenAlex ID: W2793655049
cites work: 3-coloring in time
cites work: Q4414492
cites work: Colorability of planar graphs with isolated nontriangular faces
cites work: Some simplified NP-complete graph problems
cites work: 3-coloring and 3-clique-ordering of locally connected graphs
cites work: The 3-Colorability Problem on Graphs with Maximum Degree Four
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
cites work: Q4882469
DOI: 10.1016/J.IPL.2018.02.016
Recommended article: A condition for the three colourability of planar locally path graphs
Recommended article: A Class of Three‐Colorable Triangle‐Free Graphs
Recommended article: 3-colorability of pseudo-triangulations
Recommended article: 3-coloring and 3-clique-ordering of locally connected graphs
Recommended article: Q5251923
Recommended article: Triangulating 3-Colored Graphs
Recommended article: Coloring with three‐colored subgraphs
Recommended article: Q4683143
Recommended article: Extension to 3-Colorable Triangulations
Recommended article: 3-colourability and forbidden subgraphs
description: scientific article; zbMATH DE number 6856065