𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on defective colorings of graphs in surfaces

✍ Scribed by Dan Archdeacon

Publisher
John Wiley and Sons
Year
1987
Tongue
English
Weight
139 KB
Volume
11
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is (rn, k)-colorable if its vertices can be colored with rn colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. In a recent paper Cowen. Cowen, and Woodall proved that, for each compact surface S, there exists an integer k = k(S) such that every graph in S can be (4, k)-colored. They also conjectured that the 4 could be replaced by 3. In this note we prove their conjecture.

πŸ“œ SIMILAR VOLUMES

The number of defective colorings of gra
The number of defective colorings of graphs on surfaces
✍ Tom Rackham πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 99 KB πŸ‘ 1 views

A (k, 1)-coloring of a graph is a vertex-coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least c n distinct (4, 1)-colorings, where c is constant and β‰ˆ 1.466 satisfies 3 = 2 +1. On the other hand for any >0, we gi

Note on a new coloring number of a graph
Note on a new coloring number of a graph
✍ P. HorΓ‘k; J. Ε irÑň πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 112 KB πŸ‘ 1 views

## Abstract The distance coloring number __X__~__d__~(__G__) of a graph __G__ is the minimum number __n__ such that every vertex of __G__ can be assigned a natural number __m__ ≀ __n__ and no two vertices at distance __i__ are both assigned __i__. It is proved that for any natural number __n__ ther

A Note on Almost Regular Graphs
A Note on Almost Regular Graphs
✍ M. Of Hofmeister Munich πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 136 KB

It can easily be seen that a conjecture of RUNGE does not hold for a class of graphs whose members will be called "almost regular". This conjecture is replaced by a weaker one, and a classification of almost regular graphs is given.