Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
The author's main result is a proof of a recent conjecture due to \textit{M. Karoński} and \textit{A. Ruciński} [Problem session, Graphs and other combinatorial topics, Proc. 3rd Czech. Symp., Prague 1982, Teubner-Texte Math. 59 (1983)]. Let \(G_ Y\) be the subgraph of G spanned by the subset Y of the vertex set V. Let \(m(G_ Y)\) be the number of edges of \(G_ Y\). The mean half-degree of \(G_ Y\) is defined as \(d(G_ Y)=m(G_ Y)/| Y|\). When the mean half-degree of each subgraph is at most equal to the mean half-degree of the graph G, the author calls G balanced. Moreover, let \(d_{\max}(G)\) be the maximum mean half-degree for all subgraphs of G. The conjecture that is proved reads: Every connected graph G is a subgraph of a balanced graph whose mean half- degree is \(d_{\max}(G)\).
- Transforming a graph into a 1-balanced graph
- On strongly balanced graphs
- Convex hulls of dense balanced graphs
- Fractional arboricity, strength, and principal partitions in graphs and matroids
- Extensions of matroid covering and packing
- Decomposing 4-connected planar triangulations into two trees and one path
- A property on reinforcing edge-disjoint spanning hypertrees in uniform hypergraphs
- Decomposing a graph into forests and a matching
- Every matroid is a submatroid of a uniformly dense matroid
- Packing branchings under cardinality constraints on their root sets
- Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number
- Decomposition of sparse graphs into forests and a graph with bounded degree
- Fractional spanning tree packing, forest covering and eigenvalues
- Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
- scientific article; zbMATH DE number 15501 (Why is no real title available?)
- The solution to an extremal problem on balanced extensions of graphs
- Spanning Rigid Subgraph Packing and Sparse Subgraph Covering
- Decomposing a graph into pseudoforests with one having bounded degree
- On fractional K‐factors of random graphs
- Digraph analogues for the Nine Dragon Tree Conjecture
- Balanced and 1-balanced graph constructions
- Cyclic base ordering of generalized Petersen graphs
- Cyclic base ordering of certain degenerate graphs
- Uniform density in matroids, matrices and graphs
- Characterization of removable elements with respect to having \(k\) disjoint bases in a matroid
- Decomposing a graph into forests: the nine dragon tree conjecture is true
- The arboricity of graphs with minimum genus embeddings
- Decomposing a graph into forests
This page was built for publication: Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114713)
