descriptionPublicationkeyboard_double_arrow_right Article 01 Jun 1995 English Publisher:Elsevier BVJournal:Discrete Mathematics, volume 141, pages 37-46 (issn: 0012-365X,

Authors: Paul A. Catlin; Hong-Jian Lai;

doi: 10.1016/0012-365x(93)e0205-i

Vertex arboricity and maximum degree

- Summary
- Subjects
- Related research
  (3)
- Metrics

Abstract

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\).

Related Organizations

West Virginia University Institute of Technology
United States
Wayne State College
United States
West Virginia University
United States
Wayne State University
United States

Keywords

forests, maximum degree, arboricity, Chromatic number, Arboricity, colors, Theoretical Computer Science, Vertex arboricity, Coloring of graphs and hypergraphs, chromatic number, Discrete Mathematics and Combinatorics, coloring

3 Research products, page 1 of 1

Entire colouring of plane graphs
2011IsAmongTopNSimilarDocuments
Computing Light Edges in Planar Graphs
1990IsAmongTopNSimilarDocuments
On the Entire Coloring Conjecture
2000IsAmongTopNSimilarDocuments

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	16
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average