Star Coloring of GraphsReport as inadecuate

Star Coloring of Graphs - Download this document for free, or read online. Document in PDF available to download.

1 LINA - Laboratoire d-Informatique de Nantes Atlantique 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique 3 SOCS - School of Computer Science Quebec

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 sG, is the smallest integer k for which G admits a star coloring with k colors. In this paper, we give the exact value of the star chromatic number of different families of graphs such as trees, cycles, complete bipartite graphs, outerplanar graphs and 2-dimensional grids. We also study and give bounds for the star chromatic number of other families of graphs, such as planar graphs, hypercubes, d-dimensional grids d \geq 3, d-dimensional tori d \geq 2, graphs with bounded treewidth and cubic graphs. We end this study by two asymptotic results, where we prove that, when d tends to infinity, i there exist graphs G of maximum degree d such that sG = d^{3-2}-logd^{1-2} and ii for any graph G of maximum degree d, sG = Od^{3-2}.

Author: Guillaume Fertin - André Raspaud - Bruce Reed -



Related documents