On Deeply Critical Oriented Graphs

O. V. Borodin, D. Fon-Der-Flaass, A. V. Kostochka, A. Raspaud, E. Sopena

Research output: Contribution to journalArticlepeer-review


For every positive integer k, we present an oriented graph Gk such that deleting any vertex of Gk decreases its oriented chromatic number by at least k and deleting any arc decreases the oriented chromatic number of Gk by two.

Original languageEnglish (US)
Pages (from-to)150-155
Number of pages6
JournalJournal of Combinatorial Theory. Series B
Issue number1
StatePublished - Jan 2001

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'On Deeply Critical Oriented Graphs'. Together they form a unique fingerprint.

Cite this