Colorings and orientations of graphs

N. Alon, M. Tarsi

Research output: Contribution to journalArticlepeer-review

297 Scopus citations

Abstract

Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: If G is a directed graph with maximum outdegree d, and if the number of Eulerian subgraphs of G with an even number of edges differs from the number of Eulerian subgraphs with an odd number of edges then for any assignment of a set S(v) of d+1 colors for each vertex v of G there is a legal vertex-coloring of G assigning to each vertex v a color from S(v).

Original languageEnglish (US)
Pages (from-to)125-134
Number of pages10
JournalCombinatorica
Volume12
Issue number2
DOIs
StatePublished - Jun 1 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Keywords

  • AMS Subject Classification codes (1991): 05C15, 05C20

Fingerprint Dive into the research topics of 'Colorings and orientations of graphs'. Together they form a unique fingerprint.

Cite this