On deeply critical oriented graphs
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)\).
- On the oriented chromatic number of grids
- Minimal orientations of colour critical graphs
- On the oriented chromatic number of graphs with given excess
- Homomorphisms and colourings of oriented graphs: an updated survey
- Complete oriented colourings and the oriented achromatic number
- On deeply critical oriented cliques
- Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\)
- Oriented total-coloring of oriented graphs
- On coloring parameters of triangle-free planar (n, m)-graphs
- Counting the minimum number of arcs in an oriented graph having weak diameter 2
- An update on pushable homomorphisms
This page was built for publication: On deeply critical oriented graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850516)
