✦ LIBER ✦

A note on the cover degeneracy of graphs

✍ Scribed by Li Zhang; Baoyindureng Wu

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 64 KB
Volume: 51
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20129

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We give a 4‐chromatic planar graph, which admits a vertex partition into three parts such that the union of every two of them induces a forest. This solves a problem posed by Böhme. Also, by constructing an infinite sequence of graphs, we show that the cover degeneracy can be arbitrarily less than the chromatic number. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

A note on coverings of plane graphs

✍ Eduardo Rivera-Campo 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 1 views

## Abstract For any plane graph __G__ the number of edges in a minimum edge covering of the faces of __G__ is at most the vertex independence number of __G__ and the numbre of vertices in a minimum vertex covering of the faces of __G__ is at most the edge independence number of __G__. © 1995 John W

A Graph with cover degeneracy less than

A Graph with cover degeneracy less than chromatic number

✍ A.V. Pyatkin 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 78 KB 👁 1 views

## Abstract This note contains an example of a 4‐chromatic graph which admits a vertex partition into three parts such that the union of every two of them induces a forest. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 243–246, 2001

A note on shortest cycle covers of cubic

A note on shortest cycle covers of cubic graphs

✍ Xinmin Hou; Cun-Quan Zhang 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 1 views

## Abstract Let __SCC__~3~(__G__) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph __G__. It is proved in this note that if __G__ contains no circuit of length 5 (an improvement of Jackson's (__JCTB 1994__) result: if __G__ has girth at least 7) and if all 5‐circuits of __G_

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

A note on the bichromatic numbers of gra

A note on the bichromatic numbers of graphs

✍ Dennis D. A. Epple; Jing Huang 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 2 views