𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coloring graphs with locally few colors

✍ Scribed by P Erdös; Z Füredi; A Hajnal; P Komjáth; V Rödl; Á Seress

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
832 KB
Volume
59
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a graph, m > r t> 1 integers. Suppose that it has a good-coloring with m colors which uses at most r colors in the neighborhood of every vertex. We investigate these so-called local r-colorings. One of our results (Theorem 2.4) states: The chromatic number of G, Chr(G) ~< r2" log21og2 m (and this value is the best possible in a certain sense). We consider infinite graphs as well.

📜 SIMILAR VOLUMES

Coloring a graph optimally with two colo
Coloring a graph optimally with two colors
✍ H.J. Broersma; F. Göbel 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 536 KB

Let G be a graph with point set V. A (2.)c,oloring of G is a map of V to ired, white!. An error occurs whenever the two endpoints of a line have the same color. An oprimul doring of G is a coloring of G for which the number of errors is minimum. The minimum number of errors is denoted by y(G), we de

Extending colorings of locally planar gr
Extending colorings of locally planar graphs
✍ Michael O. Albertson; Joan P. Hutchinson 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB 👁 1 views

Suppose G is a graph embedded in S g with width (also known as edge width) at least 264(2 g À 1). If P V(G) is such that the distance between any two vertices in P is at least 16, then any 5-coloring of P extends to a 5-coloring of all of G. We present similar extension theorems for 6-and 7-chromati

Coloring Locally Bipartite Graphs on Sur
Coloring Locally Bipartite Graphs on Surfaces
✍ Bojan Mohar; Paul D. Seymour 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 129 KB

It is proved that there is a function f: N Q N such that the following holds. Let G be a graph embedded in a surface of Euler genus g with all faces of even size and with edge-width \ f(g). Then (i) If every contractible 4-cycle of G is facial and there is a face of size > 4, then G is 3-colorable.

Interval edge coloring of a graph with f
Interval edge coloring of a graph with forbidden colors
✍ Marek Kubale 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 596 KB

## This paper is complementary to Kubale (1989). We consider herein a problem of interval coloring the edges of a graph under the restriction that certain colors cannot be used for some edges. We give lower and upper bounds on the minimum number of colors required for such a coloring. Since the ge