𝔖 Bobbio Scriptorium
✦   LIBER   ✦

2-distance coloring of sparse graphs

✍ Scribed by Marthe Bonamy; Benjamin Lévêque; Alexandre Pinlou

Book ID
119236550
Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
189 KB
Volume
38
Category
Article
ISSN
1571-0653

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

-coloring of sparse graphs
-coloring of sparse graphs
✍ O.V. Borodin; A.O. Ivanova; M. Montassier; A. Raspaud 📂 Article 📅 2012 🏛 Elsevier Science 🌐 English ⚖ 262 KB
-coloring of sparse graphs
-coloring of sparse graphs
✍ O.V. Borodin; A.O. Ivanova; M. Montassier; A. Raspaud 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 238 KB
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

Coloring Graphs with Sparse Neighborhood
Coloring Graphs with Sparse Neighborhoods
✍ Noga Alon; Michael Krivelevich; Benny Sudakov 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 118 KB

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.

Distance Graphs andT-Coloring
Distance Graphs andT-Coloring
✍ Gerard J Chang; Daphne D.-F Liu; Xuding Zhu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 126 KB

We discuss relationships among T-colorings of graphs and chromatic numbers, fractional chromatic numbers, and circular chromatic numbers of distance graphs. We first prove that for any finite integral set T that contains 0, the asymptotic T-coloring ratio R(T ) is equal to the fractional chromatic n