𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On coloring graphs with locally small chromatic number

✍ Scribed by H. A. Kierstead; E. Szemerédi; W. T. Trotter

Book ID
110564268
Publisher
Springer-Verlag
Year
1984
Tongue
English
Weight
123 KB
Volume
4
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Coloring graphs with locally few colors
Coloring graphs with locally few colors
✍ P Erdös; Z Füredi; A Hajnal; P Komjáth; V Rödl; Á Seress 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 832 KB

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 (an

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.

Small graphs with chromatic number 5: A
Small graphs with chromatic number 5: A computer search
✍ Tommy Jensen; Gordon F. Royle 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 402 KB

## Abstract In this article we give examples of a triangle‐free graph on 22 vertices with chromatic number 5 and a __K__~4~‐free graph on 11 vertices with chromatic number 5. We very briefly describe the computer searches demonstrating that these are the smallest possible such graphs. All 5‐critica