Vertex arboricity and maximum degree
type: Item
instance of: scholarly article
title: Vertex arboricity and maximum degree
zbMATH Open document ID: 0827.05024
DOI: 10.1016/0012-365X(93)E0205-I
author: Paul A. Catlin
author: Hong-Jian Lai
published in: Discrete Mathematics
publication date: 1995-07-24T00:00:00Z
review text: This paper mainly proves that if a connected graph \(G= (V,E)\) is neither a cycle nor a clique, then there is a coloring of \(V\) with at most \(\lceil {{\Delta (G)} \over 2} \rceil\) colors such that all color classes induce forests and one of them is a minimum induced forest in \(G\).
reviewed by: Yanpei Liu
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 778522
zbMATH Keywords: arboricity
zbMATH Keywords: maximum degree
zbMATH Keywords: chromatic number
zbMATH Keywords: coloring
zbMATH Keywords: colors
zbMATH Keywords: forests
MaRDI profile type: Publication
cites work: Q5422499
cites work: Q3201070
cites work: Brooks' graph-coloring theorem and the independence number
cites work: The point-arboricity of a graph
cites work: Q3984223
cites work: Critical Point-Arboritic Graphs
cites work: Q5530470
cites work: Bounds for the vertex linear arboricity
cites work: A short proof of Catlin's extension of Brooks' theorem
full work available at URL: 0012-365x(93)e0205-i
OpenAlex ID: W2013436809
Recommended article: Vertex arboricity and vertex degrees
Recommended article: Vertex and tree arboricities of graphs
Recommended article: On numbers of vertices of maximum degree in the spanning trees of a graph
Recommended article: Vertex arboricity of cographs
Recommended article: Q5690080
Recommended article: A Note on the Vertex Arboricity of a Graph
Recommended article: Trees with Maximum Vertex-Degree-Based Topological Indices
Recommended article: Maximal trees with bounded maximum degree in a graph
Recommended article: The Laplacian spectral radius of trees and maximum vertex degree
Recommended article: The vertex degrees of minimum spanning trees
description: scientific article; zbMATH DE number 778522