Colorings and homomorphisms of degenerate and bounded degree graphs

A. Kostochka, J. Nešetřil, P. Smolíková

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)257-276
Number of pages20
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Apr 28 2001
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Colorings and homomorphisms of degenerate and bounded degree graphs'. Together they form a unique fingerprint.

Cite this