On homomorphisms of oriented graphs with respect to the push operation

DOI10.1016/J.DISC.2016.10.023zbMATH Open1362.05089arXiv1508.07217OpenAlexW2260493414MaRDI QIDQ2397542FDOQ2397542

Authors: Sagnik Sen 

Publication date: 22 May 2017

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

Abstract: An oriented graph is a directed graph without any cycle of length at most 2. To push a vertex of a directed graph is to reverse the orientation of the arcs incident to that vertex. Klostermeyer and MacGillivray defined push graphs which are equivalence class of oriented graphs with respect to vertex pushing operation. They studied the homomorphism of the equivalence classes of oriented graphs with respect to push operation. In this article, we further study the same topic and answer some of the questions asked in the above mentioned work. The anti-twinned graph of an oriented graph is obtained by adding and pushing a copy of each of its vertices. In particular, we show that two oriented graphs are in a push relation if and only if they have isomorphic anti-twinned graphs. Moreover, we study oriented homomorphisms of outerplanar graphs with girth at least five, planar graphs and planar graphs with girth at least eight with respect to the push operation.

Full work available at URL: https://arxiv.org/abs/1508.07217

Recommendations

• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\)
• Pushable chromatic number of graphs with degree constraints
• Oriented vertex and arc colorings of outerplanar graphs
• On oriented cliques with respect to push operation

zbMATH Keywords

chromatic numbergraph homomorphismplanar graphsoriented graphspush operation

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• On acyclic colorings of planar graphs
• Negative results on acyclic improper colorings
• Acyclic colorings of planar graphs
• On the maximum average degree and the oriented chromatic number of a graph
• Good and semi-strong colorings of oriented planar graphs
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Homomorphisms and colourings of oriented graphs: an updated survey
• On oriented graphs with certain extension properties.
• The chromatic number of oriented graphs
• Homomorphism bounds for oriented planar graphs
• Oriented vertex and arc colorings of outerplanar graphs
• On reorienting graphs by pushing down maximal vertices
• Tournament games and positive tournaments
• Edge-switching homomorphisms of edge-coloured graphs
• On graphs that can be oriented as diagrams of ordered sets
• Hamiltonicity and reversing arcs in digraphs
• Re-orienting tournaments by pushing vertices.
• Pushing vertices and orienting edges
• Title not available (Why is that?)

Cited In (7)

• Pushable chromatic number of graphs with degree constraints
• Pushable chromatic number of graphs with maximum average degree at most \(\frac{14}{5}\)
• Classification of edge-critical underlying absolute planar cliques for signed graphs
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Title not available (Why is that?)
• On the pushable chromatic number of various types of grids
• On oriented cliques with respect to push operation

This page was built for publication: On homomorphisms of oriented graphs with respect to the push operation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397542)