Portal de Periódicos da CAPES

On Deeply Critical Oriented Graphs

2001; Elsevier BV; Volume: 81; Issue: 1 Linguagem: Inglês

10.1006/jctb.2000.1984

1096-0902

O. V. Borodin, D. Fon-Der-Flaass, Alexandr Kostochka, André Raspaud, Éric Sopena,

Graph Labeling and Dimension Problems

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.