On deeply critical oriented graphs
type: Item
instance of: scholarly article
title: On deeply critical oriented graphs
zbMATH Open document ID: 1025.05024
author: Oleg V. Borodin
author: Dmitry G. Fon-Der-Flaass
author: Alexandr Kostochka
author: André Raspaud
author: Éric Sopena
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: The oriented chromatic number \(o(H)\) of an oriented graph (i.e. a digraph without opposite arcs) \(H\) is the minimum order of an oriented graph \(H'\) such that \(H\) has a homomorphism to \(H'\). In other words, \(o(H)\) is the minimum positive integer \(m\) such that there exists a proper (in usual sense) colouring \(f\) of \(V(H)\) with \(m\) colours with the additional property that \[ \forall v,w,u,z\in V(H) ((vw\in E(H) \& uz\in E(H) \& f(v)= f(z))\Rightarrow f(w)\neq f(u)). \] While deleting a vertex or an edge from a graph decreases its chromatic number by at most one, this is not true for the oriented chromatic number. Call an oriented graph \(H\) deeply critical if \(o(H)- o(H- (v,u))= 2\) for every \((v,u)\in E(H)\). The main result of the note is that there are infinitely many deeply critical graphs. For every positive integer \(k\), there exists a deeply critical graph \(G_k\) such that \(o(G_k)- o(G_k- v)\geq k\) for every \(v\in V(G_k)\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1843744
zbMATH Keywords: oriented chromatic number
zbMATH Keywords: colouring
MaRDI profile type: Publication
full work available at URL: jctb.2000.1984
OpenAlex ID: W2040293809
cites work: On the maximum average degree and the oriented chromatic number of a graph
cites work: On universal graphs for planar oriented graphs of a given girth
cites work: Acyclic and oriented chromatic numbers of graphs
cites work: Colorings and girth of oriented planar graphs
cites work: The chromatic number of oriented graphs
DOI: 10.1006/JCTB.2000.1984
description: scientific article; zbMATH DE number 1843744