On homomorphisms of oriented graphs with respect to the push operation

DOI10.1016/J.DISC.2016.10.023MaRDI QIDQ2397542zbMATH OpenOpenAlexFDO

Authors Sagnik Sen

Publication date 22 May 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

Cited in

(7)

• On oriented cliques with respect to push operation
• 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
• scientific article; zbMATH DE number 2059943 (Why is no real title available?)
• On the pushable chromatic number of various types of grids

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)