Name
Abstract | ||
|---|---|---|
The vertex arboricity of graph G is the minimum number of colors that can be used to color the vertices of G so that each color class induces an acylic subraph of cyclic subgraph of G . We prove results such as this: if a connected graph G is neither a cycle nor a clique, then there is a coloring of V ( G ) with at most ⌈ Δ ( G )/2 ⌉ colors, such that each color class induces a forest and one of those induced forests is a maximum induced forest in G . This improves prior results of Brooks (1941). Kronk and Mitchem (1974/75), and Lovász (1966), and it is analogus to a result of Catlin (1976, 1979) on the chromatic number that improves Brooks' theorem. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0012-365X(93)E0205-I | Discrete Mathematics |
Keywords | Field | DocType |
vertex arboricity,maximum degree,arboricity,chromatic number,connected graph | Edge coloring,Discrete mathematics,Combinatorics,Fractional coloring,Vertex (graph theory),Neighbourhood (graph theory),Degree (graph theory),Brooks' theorem,Arboricity,Degeneracy (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
141 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
12 | 1.11 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul A. Catlin | 1 | 514 | 66.29 |
| Hong-Jian Lai | 2 | 631 | 97.39 |