Affordable Access

Publisher Website

Acyclic edge-colorings of sparse graphs

Authors
Journal
Applied Mathematics Letters
0893-9659
Publisher
Elsevier
Publication Date
Volume
7
Issue
1
Identifiers
DOI: 10.1016/0893-9659(94)90055-8

Abstract

Abstract A k-forest is a forest in which the maximum degree is k. The k-arboricity denoted A k ( G) is the minimum number of k-forests whose union is the graph G. We show that if G is an m-degenerate graph of maximum degree Δ, then A k ( G) ≤⌈(Δ+( k-1) m-1)/ k⌉, k≥2, and derive several consequences of this inequality.

There are no comments yet on this publication. Be the first to share your thoughts.