✦ LIBER ✦

Star coloring of sparse graphs

✍ Scribed by Yuehua Bu; Daniel W. Cranston; Mickaël Montassier; André Raspaud; Weifan Wang

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 174 KB
Volume: 62
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20392

No coin nor oath required. For personal study only.

✦ Synopsis

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 relationship between the star chromatic number χ~s~(G) and the maximum average degree Mad(G) of a graph G. We prove that:
If G is a graph with

, then χ~s~(G)≤4.

If G is a graph with

and girth at least 6, then χ~s~(G)≤5.

If G is a graph with

and girth at least 6, then χ~s~(G)≤6.

📜 SIMILAR VOLUMES

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.

Star coloring of graphs

✍ Guillaume Fertin; André Raspaud; Bruce Reed 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 181 KB

## Abstract A __star coloring__ of an undirected graph __G__ is a proper vertex coloring of __G__ (i.e., no two neighbors are assigned the same color) such that any path of length 3 in __G__ is not bicolored. The __star chromatic number__ of an undirected graph __G__, denoted by χ~s~(__G__), is the

Star coloring bipartite planar graphs

✍ H. A. Kierstead; André Kündgen; Craig Timmons 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

## Abstract A __star coloring__ of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eig

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

Star coloring planar graphs from small l

Star coloring planar graphs from small lists

✍ André Kündgen; Craig Timmons 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB

## Abstract A __star coloring__ of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph

Girth of sparse graphs

✍ Béla Bollobás; Endre Szemerédi 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 73 KB

## Abstract For each fixed __k__ ≥ 0, we give an upper bound for the girth of a graph of order __n__ and size __n__ + __k__. This bound is likely to be essentially best possible as __n__ → ∞. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 194–200, 2002; DOI 10.1002/jgt.10023