On universal graphs for planar oriented graphs of a given girth

DOI10.1016/S0012-365X(97)00276-8zbMath0956.05041OpenAlexW1985391430MaRDI 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 graphoriented chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items

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