@article{62babfc392eb4b08b559d905183754c5,
title = "Colorings and homomorphisms of degenerate and bounded degree graphs",
abstract = "We are interested here in homomorphisms of undirected graphs and relate them to graph degeneracy and bounded degree property. Our main result reads that both in the abundance of counterexamples and from the complexity point of view the Brooks's theorem and first fit algorithm are the 'only' easy cases.",
author = "A. Kostochka and J. Ne{\v s}et{\v r}il and P. Smol{\'i}kov{\'a}",
note = "Funding Information: ∗Corresponding author. E-mail address:
[email protected] (A. Kostochka). 1This part of the work was done while visiting Nottingham University, funded by Visiting Fellowship Research Grant GR =L54585 from the Engineering and Physical Sciences Research Council. Research was also supported in part by the grant 97-01-01075 of the Russian Foundation for Fundamental Research. 2This paper was supported in part by grants GACR* 0194 and GAUK 194 and by czech–french grant within framework Barrande.",
year = "2001",
month = apr,
day = "28",
doi = "10.1016/S0012-365X(00)00245-4",
language = "English (US)",
volume = "233",
pages = "257--276",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier B.V.",
number = "1-3",
}