Homomorphisms and oriented colorings of equivalence classes of oriented graphs

DOI10.1016/S0012-365X(03)00086-4zbMath1032.05047OpenAlexW2165426231MaRDI QIDQ1421519

William F. Klostermeyer, Gary MacGillivray

Publication date: 26 January 2004

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(03)00086-4

zbMATH Keywords

Graph homomorphismOriented chromatic numberVertex pushing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (28)

Homomorphisms and colourings of oriented graphs: an updated survey ⋮ Oriented incidence colourings of digraphs ⋮ The complexity of signed graph and edge-coloured graph homomorphisms ⋮ Unnamed Item ⋮ Semigroup theory of symmetry ⋮ On homomorphisms of oriented graphs with respect to the push operation ⋮ A complexity dichotomy for signed \(\mathbf{H}\)-colouring ⋮ On relative clique number of triangle-free planar colored mixed graphs ⋮ Analogues of cliques for \((m,n)\)-colored mixed graphs ⋮ On oriented cliques with respect to push operation ⋮ Relative clique number of planar signed graphs ⋮ The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial ⋮ Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs ⋮ On the pushable chromatic number of various types of grids ⋮ Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\) ⋮ Triangle-free projective-planar graphs with diameter two: domination and characterization ⋮ Digraph width measures in parameterized algorithmics ⋮ Pushable chromatic number of graphs with degree constraints ⋮ Homomorphisms to digraphs with large girth and oriented colorings of minimal series-parallel digraphs ⋮ Efficient computation of the oriented chromatic number of recursively defined digraphs ⋮ Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms ⋮ Sets with involutions: power group enumeration ⋮ Relative Clique Number of Planar Signed Graphs ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Edge-switching homomorphisms of edge-coloured graphs ⋮ On the oriented coloring of the disjoint union of graphs ⋮ Complexity dichotomy for oriented homomorphism of planar graphs with large girth

Cites Work

• Unnamed Item
• Unnamed Item
• The effect of two cycles on the complexity of colourings by directed graphs
• On the complexity of H-coloring
• 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
• Automorphisms and enumeration of switching classes of tournaments
• The Complexity of Colouring by Semicomplete Digraphs
• On the complexity of the general coloring problem
• Hamiltonicity and reversing arcs in digraphs
• The chromatic number of oriented graphs
• The Existence of Homomorphisms to Oriented Cycles
• Duality and Polynomial Testing of Tree Homomorphisms
• Pushing the cycles out of multipartite tournaments

This page was built for publication: Homomorphisms and oriented colorings of equivalence classes of oriented graphs