Premium
Graph Decompositions Satisfying Extremal Degree Constraints
Author(s) -
Catlin Paul A.
Publication year - 1978
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190020210
Subject(s) - combinatorics , mathematics , degree (music) , vertex (graph theory) , graph , induced subgraph , discrete mathematics , physics , acoustics
We show that the vertex set of any graph G with p ⩾2 vertices can be partitioned into non‐empty sets V 1 , V 2 , such that the maximum degree of the induced subgraph 〈 V i 〉 does not exceed\documentclass{article}\pagestyle{empty}\begin{document}$$ \frac{{p_i - 1}}{{p - 1}}\Delta (G), $$\end{document}where p i = | V i |, for i =1, 2. Furthermore, the structure of the induced subgraphs is investigated in the extreme case.