Pushable chromatic number of graphs with degree constraints
share
Pushable homomorphisms and the pushable chromatic number χ_p of oriented graphs were introduced by Klostermeyer and MacGillivray in 2004. They notably observed that, for any oriented graph G, we have χ_p(G) ≤χ_o(G) ≤ 2 χ_p(G), where χ_o(G) denotes the oriented chromatic number of G. This stands as first general bounds on χ_p. This parameter was further studied in later works.This work is dedicated to the pushable chromatic number of oriented graphs fulfilling particular degree conditions. For all Δ≥ 29, we first prove that the maximum value of the pushable chromatic number of an oriented graph with maximum degree Δ lies between 2^Δ/2-1 and (Δ-3) · (Δ-1) · 2^Δ-1 + 2 which implies an improved bound on the oriented chromatic number of the same family of graphs. For subcubic oriented graphs, that is, when Δ≤ 3, we then prove that the maximum value of the pushable chromatic number is 6 or 7. We also prove that the maximum value of the pushable chromatic number of oriented graphs with maximum average degree less than 3 lies between 5 and 6. The former upper bound of 7 also holds as an upper bound on the pushable chromatic number of planar oriented graphs with girth at least 6.
READ FULL TEXT