The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
type: Item
instance of: scholarly article
title: The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
zbMATH Open document ID: 0876.05030
DOI: 10.1016/S0096-3003(96)00021-5
author: Diamantis Koreas
published in: Applied Mathematics and Computation
publication date: 1997-11-12T00:00:00Z
review text: As is known the problem of determining the chromatic index of a cubic graph is NP-complete. In this paper, it is shown that for a triangle free graph with maximum vertex of degree 3, to determine if its chromatic index is 3 or 4 is still NP-complete.
reviewed by: Yanpei Liu
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 1006501
zbMATH Keywords: graph
zbMATH Keywords: edge-coloring
zbMATH Keywords: chromatic index
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
cites work: Q3941433
cites work: The NP-Completeness of Edge-Coloring
cites work: Using euler partitions to edge color bipartite multigraphs
cites work: Q4198056
full work available at URL: s0096-3003(96)00021-5
OpenAlex ID: W2044028427
description: scientific article; zbMATH DE number 1006501