
doi: 10.7151/dmgt.1237
Considered are subgraphs of oriented graphs in the context of oriented colouring that are analogous to cliques in traditional vertex colouring. Bounds on the sizes of these subgraphs are given for planar, outerplaner and series-parallel graphs. The authors show, among other things, that a planar graph cannot contain an induced subgraph \(D\) with more than 36 vertices such that each pair of vertices in \(D\) are joined by a directed path of length at most two. The following conjecture is stated. Let \(D\) be an orientation of a planar graph such that for any two vertices \(x\), \(y\in V(G)\) there exists an \(xy/yx\) directed path of length at most two. Then \(D\) has at most fifteen vertices.
colouring, Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), planar graph, Directed graphs (digraphs), tournaments, orientation
colouring, Coloring of graphs and hypergraphs, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), planar graph, Directed graphs (digraphs), tournaments, orientation
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 21 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
