Name
Abstract | ||
|---|---|---|
The strong chromatic number, $\chi_S(G)$, of an $n$-vertex graph $G$ is the smallest number $k$ such that after adding $k\lceil n/k\rceil - n$ isolated vertices to $G$ and considering any partition of the vertices of the resulting graph into disjoint subsets $V_1, \ldots, V_{\lceil n/k\rceil}$ of size $k$ each, one can find a proper $k$-vertex-coloring of the graph such that each part $V_i$, $i=1, \ldots, \lceil n/k\rceil$, contains exactly one vertex of each color. For any graph $G$ with maximum degree &Dgr;, it is easy to see that $\chi_S(G) \geq \Delta + 1$. Recently, Haxell proved that $\chi_S(G) \leq 3\Delta - 1$. In this paper, we improve this bound for graphs with large maximum degree. We show that $\chi_S(G) \leq 2\Delta$ if $\Delta \geq n/6$ and prove that this bound is sharp. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1137/050633056 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
isolated vertex,maximum degree,geq n,lceil n,strong chromatic number,disjoint subsets,large maximum degree,resulting graph,smallest number,vertex graph,transversals | Discrete mathematics,Graph,Combinatorics,Disjoint sets,Vertex (geometry),Chromatic scale,Vertex (graph theory),Transversal (geometry),Degree (graph theory),Partition (number theory),Mathematics | Journal |
Volume | Issue | ISSN |
20 | 3 | SIAM J. Discrete Math. 20(3) (2006), 741--747 |
Citations | PageRank | References |
5 | 0.55 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Axenovich | 1 | 209 | 33.90 |
| Ryan Martin | 2 | 144 | 14.43 |