๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The number of defective colorings of graphs on surfaces

โœ Scribed by Tom Rackham

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
99 KB
Volume
68
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 give examples of planar graphs with fewer than c(+ ) n distinct (4, 1)-colorings, where c is constant and = (1+ โˆš 5) / 2. Let (S) denote the chromatic number of a surface S. For every surface S except the sphere, we show that there exists a constant c = c (S)>0 such that every graph embeddable in S has at least c 2 n distinct ( (S), 1)-colorings. แญง

๐Ÿ“œ SIMILAR VOLUMES

A note on defective colorings of graphs
A note on defective colorings of graphs in surfaces
โœ Dan Archdeacon ๐Ÿ“‚ Article ๐Ÿ“… 1987 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 139 KB ๐Ÿ‘ 2 views

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 eve

On the Number of 3-Edge Colorings of Cub
On the Number of 3-Edge Colorings of Cubic Graphs
โœ Christian Szegedy ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 127 KB

In this paper we present a short algebraic proof for a generalization of a formula of R. Penrose, Some applications of negative dimensional tensors, in: Combinatorial Mathematics and its Applications Welsh (ed.), Academic Press, 1971, pp. 221-244 on the number of 3-edge colorings of a plane cubic gr

Maximum number of colorings of (2k, k2)-
Maximum number of colorings of (2k, k2)-graphs
โœ Felix Lazebnik; Oleg Pikhurko; Andrew Woldar ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 168 KB ๐Ÿ‘ 1 views

## Abstract Let ${\cal F}\_{{2}{k},{k}^{2}}$ consist of all simple graphs on 2__k__ vertices and ${k}^{2}$ edges. For a simple graph __G__ and a positive integer $\lambda$, let ${P}\_{G}(\lambda)$ denote the number of proper vertex colorings of __G__ in at most $\lambda$ colors, and let $f(2k, k^{2

On Total Colorings of Graphs
On Total Colorings of Graphs
โœ C. Mcdiarmid; B. Reed ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 299 KB

AND Bruce Reed Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada

On the number of list-colorings
On the number of list-colorings
โœ Quentin Donner ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 249 KB

## Abstract Given a __list of boxes L__ for a graph __G__ (each vertex is assigned a finite set of colors that we call a box), we denote by __f__(__G, L__) the number of Lโ€__colorings__ of __G__ (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and