Hell, P.; Kostochka, A. V.; Raspaud, A.; Sopena, E. On nice graphs. (English) Zbl 0990.05058 Discrete Math. 234, No. 1-3, 39-51 (2001). 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. Reviewer: Matúš Harminc (Košice) Cited in 2 ReviewsCited in 9 Documents MSC: 05C20 Directed graphs (digraphs), tournaments 05C15 Coloring of graphs and hypergraphs Keywords:graph homomorphisms; oriented graphs; edge-coloured graphs; universal graphs; characterizations; chromatic number; nice graphs PDFBibTeX XMLCite \textit{P. Hell} et al., Discrete Math. 234, No. 1--3, 39--51 (2001; Zbl 0990.05058) Full Text: DOI