On universal graphs for planar oriented graphs of a given girth

DOI10.1016/S0012-365X(97)00276-8zbMath0956.05041MaRDI QIDQ1584330

Alexandr V. Kostochka, Oleg V. Borodin, Andre Raspaud, Jaroslav Nešetřil, Eric Sopena

Publication date: 2 November 2000

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(97)00276-8

zbMATH Keywords

oriented graph; oriented chromatic number

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C20: Directed graphs (digraphs), tournaments

Related Items

On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets, Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\), Homomorphisms and colourings of oriented graphs: an updated survey, On induced-universal graphs for the class of bounded-degree graphs, On the oriented chromatic number of grids, Antisymmetric flows and strong colourings of oriented graphs, Homomorphisms from sparse graphs with large girth., On deeply critical oriented graphs, Nilpotent families of endomorphisms of \((\mathcal P(V)^+,\cup)\), Homomorphisms of planar \((m,n)\)-colored-mixed graphs to planar targets, Complexity dichotomy for oriented homomorphism of planar graphs with large girth

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Universality of \(A\)-mote graphs
• On the maximum average degree and the oriented chromatic number of a graph
• Good and semi-strong colorings of oriented planar graphs
• Colorings and girth of oriented planar graphs
• Acyclic and oriented chromatic numbers of graphs
• The chromatic number of oriented graphs
• Duality and Polynomial Testing of Tree Homomorphisms
• 25 pretty graph colouring problems