Premium
Uniquely Partitionable Graphs
Author(s) -
Bollobás B.,
Thomason A. G.
Publication year - 1977
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-16.3.403
Subject(s) - combinatorics , mathematics , partition (number theory) , graph , vertex (graph theory) , induced subgraph , discrete mathematics
A graph is l ‐degenerate if it does not contain a subgraph whose minimum degree is greater than l .A ( k , l )‐partition of a graph G is a partition of the vertex set V(G) of G into k subsets V 1 ,.., V k , such that each V l induces an l ‐degenerate graph. A graph with exactly one ( k , l )‐partition is said to be uniquely ( k , l )‐partitionable. Extending a number of earlier results, we prove that for every k , l and g there are non‐trivial uniquely ( k , l )‐partitionable graphs of girth at least g .