Partitions of graphs with high minimum degree or connectivity.

*(English)*Zbl 1045.05075In 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.

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.

Reviewer: Ludovit Niepel (Safat)

##### MSC:

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

05C40 | Connectivity |

PDF
BibTeX
XML
Cite

\textit{D. Kühn} and \textit{D. Osthus}, J. Comb. Theory, Ser. B 88, No. 1, 29--43 (2003; Zbl 1045.05075)

Full Text:
DOI

##### References:

[1] | Alon, N.; Spencer, J., The probabilistic method, (2000), Wiley-Interscience New York |

[2] | Bollobás, B.; Scott, A.D., Exact bounds for judicious partitions of graphs, Combinatorica, 19, 473-486, (1999) · Zbl 0985.05028 |

[3] | R. Diestel, Graph Theory, Graduate Texts in Mathematics, Vol. 173, Springer, Berlin, 1997. |

[4] | Hajnal, P., Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, 3, 95-99, (1983) · Zbl 0529.05030 |

[5] | Kriesell, M., Induced paths in 5-connected graphs, J. graph theory, 36, 52-58, (2001) · Zbl 0977.05074 |

[6] | D. Kühn, D. Osthus, Induced subdivisions in Ks,s-free graphs of large average degree, Combinatorica, to appear. |

[7] | Larman, D.G.; Mani, P., On the existence of certain configurations within graphs and the 1-skeletons of polytopes, Proc. London math. soc, 20, 144-160, (1970) · Zbl 0201.56801 |

[8] | Porter, T.D., Graph partitions, J. combin. math. combin. comput, 15, 111-118, (1994) · Zbl 0806.05032 |

[9] | Stiebitz, M., Decomposing graphs under degree constraints, J. graph theory, 23, 321-324, (1996) · Zbl 0865.05058 |

[10] | Thomassen, C., Non-separating cycles in k-connected graphs, J. graph theory, 5, 351-354, (1981) · Zbl 0498.05044 |

[11] | Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. graph theory, 7, 165-167, (1983) · Zbl 0515.05045 |

[12] | Thomassen, C., Graph decomposition with applications to subdivisions and path systems modulo k, J. graph theory, 7, 261-271, (1983) · Zbl 0515.05052 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.