Computational complexity of \((2,2)\) path chromatic number problem
type: Item
instance of: scholarly article
title: Computational complexity of \((2,2)\) path chromatic number problem
zbMATH Open document ID: 0837.05056
DOI: 10.1007/BF02663898
author: Jinjiang Yuan
published in: Applied Mathematics. Series B (English Edition)
publication date: 1996-05-13T00:00:00Z
review text: The \((k,r)\) path chromatic number problem is the problem of checking whether vertices of a graph can be colored with \(r\) colors in such a way that each component of the subgraph induced by vertices of any color is a path of order at most \(k\). The author shows that the (2, 2) path chromatic number problem for graphs with maximum degree 4 is NP-complete.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 763886
zbMATH Keywords: path chromatic number problem
zbMATH Keywords: path
zbMATH Keywords: NP-complete
reviewed by: Dragoš Cvetković
MaRDI profile type: Publication
cites work: Path chromatic numbers of graphs
cites work: Q4198056
full work available at URL: https://doi.org/10.1007/bf02663898
OpenAlex ID: W2329110168
description: scientific article; zbMATH DE number 763886