On push chromatic number of planar graphs and planar p-cliques
Sagnik Sen · Scuola Normale Superiore eBooks · 2013
An oriented graph ̅G is a directed graph without cycles of length 1 or 2. Pushing a vertex v of an oriented graph ̅G is to change the orientation of all its arcs (replacing the arc ̅xy by ̅yx) incident to v. If we can obtain ̅G2 by pushing some vertices of ̅G1 then, the two graphs are in an equivalence relation called push relation. A push graph ̅G 2 is an equivalance class of oriented graphs (̅G is an element of the class) with respect to push relation.