Partitions of graphs with high minimum degree or connectivity. (Q1405098)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partitions of graphs with high minimum degree or connectivity. |
scientific article |
Statements
Partitions of graphs with high minimum degree or connectivity. (English)
0 references
25 August 2003
0 references
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.
0 references
graph partitions
0 references
minimum degree
0 references
connectivity
0 references
0 references