Graphes équilibrés et arboricité rationnelle. (Balanced graphs and rational arboricity) (Q1114713): Difference between revisions

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