Fetching the paper…

Reading the bibliography…

Improved bounds on coloring of graphs · Around

2010

Improved bounds on coloring of graphs

Ndreca, Sokol, Procacci, Aldo, Scoppola, Benedetto

Original
PDF
Post on X

Understand

Given a graph $G$ with maximum degree $\Delta\ge 3$, we prove that the acyclic edge chromatic number $a'(G)$ of $G$ is such that $a'(G)\le\lceil 9.62 (\Delta-1)\rceil$.

Moreover we prove that: $a'(G)\le \lceil 6.42(\Delta-1)\rceil$ if $G$ has girth $g\ge 5\,$; $a'(G)\le \lceil5.77 (\Delta-1)\rc$ if $G$ has girth $g\ge 7$; $a'(G)\le \lc4.52(\D-1)\rc$ if $g\ge 53$; $a'(G)\le \D+2\,$ if $g\ge \lceil25.84\D\log\D(1+ 4.1/\log\D)\rceil$.
We further prove that the acyclic (vertex) chromatic number $a(G)$ of $G$ is such that $a(G)\le \lc 6.59 \Delta^{4/3}+3.3\D\rc$.
We also prove that the star-chromatic number $\chi_s(G)$ of $G$ is such that $\chi_s(G)\le \lc4.34\Delta^{3/2}+ 1.5\D\rc$.

Built on

Vizing, V. G.:
1964
Earlier work this paper cites.
Erdös, P. and Lovász, L.:
1975
Earlier work this paper cites.
Shearer, J. B.:
1985
Earlier work this paper cites.
Alon, N. Mc Diarmid, C.; Reed, B.:
1991
Earlier work this paper cites.
Dobrushin, R. L.:
1996
Earlier work this paper cites.
Hind, H. Molloy, M., Reed, B.:
1997
Earlier work this paper cites.
Molloy, M.; Reed, B.;
1998
Earlier work this paper cites.

Similar

Alon, N.; Sudakov, B.; Zaks, A.:
2001
Cited alongside, same era.
Sokal, A. D.:
2001
Cited alongside, same era.
Fertin G.; Raspaud, A.; Reed, B.:
2004
Cited alongside, same era.
Scott, A.; Sokal, A. D.:
2005
Cited alongside, same era.
Fernández, R.; Procacci A.:
2007
Cited alongside, same era.
Muthu, R.; Narayanan, N.; Subramanian, C.R.:
2007
Cited alongside, same era.
Muthu, R.; Narayanan, N.; Subramanian, C.R.:
2007
Cited alongside, same era.
Pegden, W.:
Cited in the paper.

Then

Alon, N. and Spencer, J.:
2008
Later among the works it cites.
Fernández, R.; Procacci A.:
2008
Later among the works it cites.
Basavarajua, M.; Sunil Chandran, L.:
2009
Later among the works it cites.
Basavarajua, M.; Sunil Chandran, L.:
2009
Later among the works it cites.
Moser, R. ; Tardos, G.:
2010
Closest in time.
Bissacot, R.; Fernández, R.; Procacci, A.; Scoppola, B.:
2011
Closest in time.
Böttcher, J.; Kohayakawa, Y, Procacci, A,:
2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…