𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on group colorings

✍ Scribed by Daniel Král'; Ondřej Pangrác; Heinz-Jürgen Voss

Publisher
John Wiley and Sons
Year
2005
Tongue
English
Weight
83 KB
Volume
50
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We study a concept of group coloring introduced by Jaeger et al. We show that the group chromatic number of a graph with minimum degree δ is greater than δ/(2, ln δ) and we answer several open questions on the group chromatic number of planar graphs: a construction of a bipartite planar graph with group chromatic number four and a 3‐colorable planar graph with group chromatic number five are presented. We also observe that several upper bounds on the choice number for various subclasses of planar graphs also translate to the concept of group colorings. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

A note on list-colorings
A note on list-colorings
✍ Amanda Chetwynd; Roland Häggkvist 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

In this article we discuss the current results on the list chromatic conjecture and prove that if G is a triangle free graph with maximum degree A then xi(G) 5 9A/5. If the term "a classic" can be used about a mathematical problem less than 10 years old, then surely the following question by Jeff D

A Note on Graph Colorings and Graph Poly
A Note on Graph Colorings and Graph Polynomials
✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

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

A Note on Frobenius Groups
A Note on Frobenius Groups
✍ Paul Flavell 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 87 KB

Two celebrated applications of the character theory of finite groups are Burnside's p ␣ q ␤ -Theorem and the theorem of Frobenius on the groups that bear his name. The elegant proofs of these theorems were obtained at the beginning of this century. It was then a challenge to find character-free proo

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