E-resources
Peer reviewed
-
Bonamy, Marthe; Kelly, Tom; Nelson, Peter; Postle, Luke
Journal of combinatorial theory. Series B, November 2022, 2022-11-00, Volume: 157Journal Article
The greedy coloring algorithm shows that a graph of maximum degree at most Δ has chromatic number at most Δ+1, and this is tight for cliques. Much attention has been devoted to improving this “greedy bound” for graphs without large cliques. Brooks famously proved that this bound can be improved by one if Δ≥3 and the graph contains no clique of size Δ+1. Reed's Conjecture states that the “greedy bound” can be improved by k if the graph contains no clique of size Δ+1−2k. Johansson proved that the “greedy bound” can be improved by a factor of Ω(ln(Δ)−1) or Ω(ln(ln(Δ))ln(Δ)) for graphs with no triangles or no cliques of any fixed size, respectively. Notably missing is a linear improvement on the “greedy bound” for graphs without large cliques. In this paper, we prove that for sufficiently large Δ, if G is a graph with maximum degree at most Δ and no clique of size ω, thenχ(G)≤72Δln(ω)ln(Δ). This implies that for sufficiently large Δ, if ω(72c)2≤Δ then χ(G)≤Δ/c. This bound actually holds for the list-chromatic and even the correspondence chromatic number (also known as DP-chromatic number). In fact, we prove what we call a “local version” of it, a result implying the existence of a coloring when the number of available colors for each vertex depends on local parameters, like the degree and the clique number of its neighborhood. We prove that for sufficiently large Δ, if G is a graph of maximum degree at most Δ and minimum degree at least ln2(Δ) with list-assignment L, then G is L-colorable if for each v∈V(G),|L(v)|≥72deg(v)⋅min{ln(ω(v))ln(deg(v)),ω(v)ln(ln(deg(v)))ln(deg(v)),log2(χ(v)+1)ln(deg(v))}, where χ(v) denotes the chromatic number of the neighborhood of v and ω(v) denotes the size of a largest clique containing v. This simultaneously implies the linear improvement over the “greedy bound” and the two aforementioned results of Johansson.
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.