## Abstract

A digraph G is k-nice for some positive integer k if for every two (not necessarily distinct) vertices x and y in G and every pattern of length k, given as a sequence of pluses and minuses, there exists a walk of length k linking x to y which respects this pattern (pluses corresponding to forward edges and minuses to backward edges). A digraph is then nice if it is k-nice for some k. Similarly, a multigraph H, whose edges are coloured by a set of p colours, is k-nice if for every two (not necessarily distinct) vertices x and y in H and every pattern of length k, given as a sequence of colours, there exists a path of length k linking x to y which respects this pattern. Such a multigraph is nice if it is k-nice for some k. In this paper we study the structure of nice digraphs and multigraphs.

Original language | English (US) |
---|---|

Pages (from-to) | 39-51 |

Number of pages | 13 |

Journal | Discrete Mathematics |

Volume | 234 |

Issue number | 1-3 |

DOIs | |

State | Published - May 6 2001 |

## Keywords

- Edge-coloured graphs
- Graph homomorphisms
- Oriented graphs
- Universal graphs

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics