On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree

Min Chen, Weiqiang Yu and Weifan Wang

Applied Mathematics and Computation, 2018, vol. 326, issue C, 117-123

Abstract: Given a graph G=(V,E), if its vertex set V(G) can be partitioned into two non-empty subsets V1 and V2 such that G[V1] is edgeless and G[V2] is a graph with maximum degree at most k, then we say that G admits an (I, Δk)-partition. A similar definition can be given for the notation (I, Fk)-partition if G[V2] is a forest with maximum degree at most k.

Keywords: Vertex partition; Maximum average degree; Forest; Girth (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300318300092
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:326:y:2018:i:c:p:117-123

DOI: 10.1016/j.amc.2018.01.003

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().