Covering the vertex set of a graph with subgraphs of smaller degree |
| |
Authors: | Jim Lawrence |
| |
Affiliation: | Department of Mathematics, University of Texas at Austin, Austin, TX 78712, U.S.A. |
| |
Abstract: | The problem of covering the vertex set of a graph with subsets spanning subgraphs of smaller degree is studied. The result of this study is applied to give a new bound on the chromatic number of a graph in terms of the maximum vertex-degree of the graph and the maximum number of vertices in a clique of the graph. By using this bound, it is shown that if d is at least 7 and e is at least 4, then there is no regular graph of valency d, chromatic number d, whose smallest circuit has at least e edges; this settles a conjecture of Branko Grünbaum. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|