Pushable chromatic number of graphs with degree constraints (Q2219941)

An oriented graph \(\overset{\rightarrow}{G}\) is a loopless digraph withour opposite edges. The oriented chromatic number of \(\overset{\rightarrow}{G}\), denoted \(\chi_o(\overset{\rightarrow}{G})\), is the minimum order of an orientged graph \(\overset{\rightarrow}{H}\) such that there exists a homomorphism \(\overset{\rightarrow}{G}\rightarrow\overset{\rightarrow}{H}\). Two graphs \(\overset{\rightarrow}{G}\) and \(\overset{\rightarrow}{G^\prime}\) are in push relation if one can be transformed into the other by pushing some vertices, where pushing a vertex means changing the orientation of all the arcs incident to it. The pushable chromatic number of \(\overset{\rightarrow}{G}\), denoted \(\chi_p(\overset{\rightarrow}{G})\), is the minimum order of an orientged graph \(\overset{\rightarrow}{H}\) such that there exists a homomorphism \(\overset{\rightarrow}{G^\prime}\rightarrow\overset{\rightarrow}{H}\) for some \(\overset{\rightarrow}{G^\prime}\) being in push relation with \(\overset{\rightarrow}{G}\). It has been known that \(\chi_p(\overset{\rightarrow}{G})\leq\chi_o(\overset{\rightarrow}{G})\leq2\chi_p(\overset{\rightarrow}{G})\) for every oriented graph \(\overset{\rightarrow}{G}\). The authors consider the degree-constrained families of graphs and prove in particular that for every connected graph \(\overset{\rightarrow}{G}\) with \(\Delta\geq 29\), \(2^{\Delta/2-1}\leq \chi_p(\overset{\rightarrow}{G})\leq (\Delta-3)(\Delta-1)2^{\Delta-1}+2\) and \(2^{\Delta/2}\leq \chi_o(\overset{\rightarrow}{G})\leq (\Delta-3)(\Delta-1)2^{\Delta}+2\). For graphs with maximum degree \(\Delta=3\), one has \(6\leq \chi_p(\overset{\rightarrow}{G})\leq 7\), while in the case of graphs with maximum average degree \(\operatorname{mad}(G)<3\), \(5\leq \chi_p(\overset{\rightarrow}{G})\leq 7\) holds. Finally, planar graphs with girth at leasy \(6\) satisfy \(4\leq \chi_p(\overset{\rightarrow}{G})\leq 7\).