𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coloring Graphs with Sparse Neighborhoods

✍ Scribed by Noga Alon; Michael Krivelevich; Benny Sudakov

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
118 KB
Volume
77
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 Γ‚f is at most O(dΓ‚log f ). This is tight (up to a constant factor) for all admissible values of d and f.

πŸ“œ SIMILAR VOLUMES

Star coloring of sparse graphs
Star coloring of sparse graphs
✍ Yuehua Bu; Daniel W. Cranston; MickaΓ«l Montassier; AndrΓ© Raspaud; Weifan Wang πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 174 KB

## Abstract A proper coloring of the vertices of a graph is called a __star coloring__ if the union of every two color classes induces a star forest. The star chromatic number Ο‡~__s__~(__G__) is the smallest number of colors required to obtain a star coloring of __G__. In this paper, we study the r

Dense Graphs with Cycle Neighborhoods
Dense Graphs with Cycle Neighborhoods
✍ A. Seress; T. Szabo πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 420 KB

For all \(\varepsilon>0\), we construct graphs with \(n\) vertices and \(>n^{2-n}\) edges, for arbitrarily large \(n\), such that the neighborhood of each vertex is a cycle. This result is asymptotically best possible. "1995 Academic Press. Inc.

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

Class of graphs with restricted neighbor
Class of graphs with restricted neighborhoods
✍ Kim T. Rawlinson; R. C. Entringer πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 286 KB

## Abstract A description is obtained for connected graphs in which a point __u__ is adjacent of __v__ only if __u__ is adjacent to all points whose degree is greater than that of __v__. The minimum number of lines in such a grpah with all points having degree at least __d__ is also determined. Fin

Coloring plane graphs with independent c
Coloring plane graphs with independent crossings
✍ Daniel KrΓ‘l'; Ladislav Stacho πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 268 KB

## Abstract We show that every plane graph with maximum face size four in which all faces of size four are vertex‐disjoint is cyclically 5‐colorable. This answers a question of Albertson whether graphs drawn in the plane with all crossings independent are 5‐colorable. Β© 2009 Wiley Periodicals, Inc.