On the genus of graphs with Lick-White number π
John Mitchem Β· Proceedings of the American Mathematical Society Β· 1978
A graph is called n -degenerate if each of its subgraphs has a vertex of degree at most n . For each n the Lick-White number of graph G is the fewest number of sets into which V ( G ) V(G) can be partitioned such that each set induces an n -degenerate graph. An upper bound is obtained for the Lick-White number of graphs with given clique number. A number of estimates are derived for the number of vertices in triangle-free graphs with prescribed Lick-White number. These results are used to give lower bounds on the genus of such graphs.