On the colorability of \(m\)-composed graphs
type: Item
instance of: scholarly article
title: On the colorability of \(m\)-composed graphs
zbMATH Open document ID: 0809.05043
DOI: 10.1016/0012-365X(94)90025-6
author: R. Klein
published in: Discrete Mathematics
publication date: 1995-03-20T00:00:00Z
review text: A graph is said to be \(m\)-degenerated if each of its subgraphs has the minimum degree at most \(m\). If a graph is the union of an \(m\)-degenerated graph and an acyclic graph, then it is called \(m\)-composed. This paper provides a conjecture that any \(m\)-composed graph is \(k\)-colorable, where \(k= m+1+\) the integral part of the half of \(1+ \sqrt{8m+1}\). In support of this, many \((k+1)\)-chromatic graphs are shown not to be \(m\)-composed.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 681697
zbMATH Keywords: graph coloring
zbMATH Keywords: colorability
zbMATH Keywords: \(m\)-degenerated graph
zbMATH Keywords: \(m\)-composed graph
reviewed by: Yanpei Liu
MaRDI profile type: Publication
cites work: Q5528475
cites work: Nowhere-zero 6-flows
cites work: Colour-critical graphs and hypergraphs
full work available at URL: 0012-365x(94)90025-6
OpenAlex ID: W2050738054
description: scientific article; zbMATH DE number 681697