An intermediate value theorem for the arboricities
type: Item
instance of: scholarly article
title: An intermediate value theorem for the arboricities
zbMATH Open document ID: 1237.05160
DOI: 10.1155/2011/947151
author: Avapa Chantasartrassmee
author: N. Punnim
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 2011-07-22T00:00:00Z
review text: Summary: Let \(G\) be a graph. The vertex (edge) arboricity of \(G\), denoted by \(a(G)\) (\(a_1(G)\)), is the minimum number of subsets into which the vertex (edge) set of \(G\) can be partitioned so that each subset induces an acyclic subgraph. Let \(d\) be a graphical sequence and let \({\mathcal{R}}(d)\) be the class of realizations of \(d\). We prove that if \(\pi \in \{a,a_1\}\), then there exist integers \(x(\pi)\) and \(y(\pi)\) such that \(d\) has a realization \(G\) with \(\pi(G) = z\) if and only if \(z\) is an integer satisfying \(\pi(z) \leq z \leq y(z)\). Thus, for an arbitrary graphical sequence \(d\) and \(\pi \in \{a,a_1\}\), the two invariants \(x(\pi) = \min(\pi,d) := \min\{\pi(G) : G \in \mathcal{R}(d)\}\) and \(y(\pi) \max(\pi,d) := \max\{\pi(G) : G \in \mathcal{R}(d)\}\) naturally arise and hence \(\pi(d) := \{\pi(G) : G \in \mathcal{R}(d)\} = \{z \in \mathbb{Z} : x(\pi) \leq z \leq y(\pi)\}\). We write \(d = r^n := (r,r,\dots,,r)\) for the degree sequence of an \(r\)-regular graph of order \(n\). We prove that \(a_1(r^n) = \{\lceil(r+1)/2\rceil\}\). We consider the corresponding extremal problem on vertex arboricity and obtain \(\min(a,r^n)\) in all situations and \(\max(a,r^n)\) for all \(n \geq 2r + 2\) .
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C07
zbMATH DE Number: 5930229
Wikidata QID: Q58687994
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2011/947151
OpenAlex ID: W2069576528
cites work: Q3158579
cites work: Graphs with forbidden subgraphs
cites work: Decomposition of Finite Graphs Into Forests
cites work: COVERING AND PACKING IN GRAPHS, I.
cites work: Q3907606
cites work: A remark on the existence of finite graphs
cites work: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
cites work: Q3025209
cites work: Some Theorems on Abstract Graphs
cites work: The Point-Arboricity of Planar Graphs
DBLP publication ID: journals/ijmmsc/ChantasartrassmeeP11
Recommended article: Q3765795
Recommended article: Q4894966
Recommended article: A fixed-point theorem for trees
Recommended article: Q5445633
Recommended article: Some results on linear arboricity
Recommended article: Q3201068
Recommended article: On a problem of linear arboricity
Recommended article: A note on disjoint arborescences
Recommended article: Towards the linear arboricity conjecture
Recommended article: A planar linear arboricity conjecture
description: scientific article; zbMATH DE number 5930229