On nice graphs (Q5936050)

A digraph \(D=(V,A)\) is called \(k\)-nice (\(k\)-half-nice) if there exists a positive integer \(k\) such that for every two (not necessarily distinct) vertices \(x,y\) and for every given sequence \(q=(q_1,\dots,q_k)\in\{+,-\}^k,\) there exists a walk in \(D\) starting from \(x\) to \(y\) (starting from \(x\) containing \(y\)) which respects \(q,\) i.e. \(q_i=+\) corresponds to a forward arc and \(q_i=-\) to a backward one. Nice and half-nice multigraphs with \(p\)-coloured edges are defined similarly. The authors obtained several characterizations of the structure of nice and half-nice digraphs, and of nice and half-nice multigraphs. They found minimal numbers of arcs in nice and half-nice digraphs, and minimal numbers of edges in nice and half-nice multigraphs for the given number of vertices. The study of nice graphs is motivated by the problem of determining the oriented chromatic number of some graphs. A graph \(G\) is universal for some class \(C\) of graphs if every graph \(H\in C\) has a homomorphism to \(G.\) Results connecting nice graphs and universal graphs for some classes of planar or outerplanar graphs are included.