Partitions of graphs with high minimum degree or connectivity. (Q1405098): Difference between revisions

In the paper partitions of graphs with high connectivity into high connected subgraphs with some additional property are investigated. It is proved that for any integer \(l\) there exists a value \(f(l)\) such that the vertex set of any \(f(l)\)-connected graph can be partioned into sets \(S\) and \(T\) where the induced graphs \(G[S]\) and \(G[T]\) are both \(l\)-connected and every vertex of \(S\) is adjacent to at least \(l\) vertices in \(T\). In an analogous result the minimum degree \(h(l)\) of a graph \(G\) guarantees a partition \((S,T)\) of its vertex set such that both subgraphs \(G[S]\) and \(G[T]\) have minimum degree at least \(l\) and every vertex of \(S\) is adjacent to at least \(l\) vertices in \(T\). In the paper are also proved results for partitions of a graph when constraints are based on the average degrees or chromatic numbers.