Star arboricity of graphs

被引：38

作者：

Hakimi, SL

Mitchem, J

Schmeichel, E

机构：

[1] UNIV CALIF DAVIS,DEPT ELECT & COMP ENGN,DAVIS,CA 95616

[2] SAN JOSE STATE UNIV,DEPT MATH & COMP SCI,SAN JOSE,CA 95192

来源：

DISCRETE MATHEMATICS | 1996年 / 149卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0012-365X(94)00313-8

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We develop a connection between vertex coloring in graphs and star arboricity which allows us to prove that every planar graph has star arboricity at most 5. This settles an open problem raised independently by Algor and Alon and by Ringer. We also show that deciding if a graph has star arboricity 2 is NP-complete, even for 2-degenerate graphs.

引用

页码：93 / 98

页数：6

共 10 条

[1]

Akiyama J., 1985, GRAPHS APPL, P1

[2] THE STAR ARBORICITY OF GRAPHS [J].