✦ LIBER ✦

Random coloring evolution on graphs

✍ Scribed by Xin Xing Chen; Jian Gang Ying

Publisher: Institute of Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society
Year: 2010
Tongue: English
Weight: 178 KB
Volume: 26
Category: Article
ISSN: 1439-7617
DOI: 10.1007/s10114-010-6286-9

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On-Line Coloring of Sparse Random Graphs

On-Line Coloring of Sparse Random Graphs and Random Trees

✍ Boris Pittel; Robert S. Weishaar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 164 KB

The performance of the greedy coloring algorithm ''first fit'' on sparse random graphs G and on random trees is investigated. In each case, approximately n, c r n log log n colors are used, the exact number being concentrated almost surely on at 2 most two consecutive integers for a sparse random gr

Algorithms for coloring semi-random grap

Algorithms for coloring semi-random graphs

✍ C. R. Subramanian; Martin Fürer; C. E. Veni Madhavan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 3 views

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-co

List Coloring of Random and Pseudo-Rando

List Coloring of Random and Pseudo-Random Graphs

✍ Noga Alon; Michael Krivelevich; Benny Sudakov 📂 Article 📅 1999 🏛 Springer-Verlag 🌐 English ⚖ 317 KB

Online vertex-coloring games in random g

Online vertex-coloring games in random graphs

✍ Martin Marciniszyn; Reto Spöhel 📂 Article 📅 2010 🏛 Springer-Verlag 🌐 English ⚖ 541 KB

Randomized online graph coloring

✍ Sundar Vishwanathan 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 793 KB

On list-coloring outerplanar graphs

✍ Joan P. Hutchinson 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

## Abstract We prove that a 2‐connected, outerplanar bipartite graph (respectively, outerplanar near‐triangulation) with a list of colors __L__ (__v__ ) for each vertex __v__ such that $|L(v)|\geq\min\{{\deg}(v),4\}$ (resp., $|L(v)|\geq{\min}\{{\deg}(v),5\}$) can be __L__‐list‐colored (except when