A note on orientation and chromatic number of graphs (Q2410109): Difference between revisions

Let \(G\) be a simple and finite graph, and let \(D\) be an orientation of \(G\). If \(D\) has a directed path of order \(k\), then define \(\Delta_k(D)\) to be the maximum value \(t\) for which a directed path \(v_1\dots v_k\) in \(D\) satisfies that the outdegree of \(v_k\) in \(D\) is \(t\); otherwise, define \(\Delta_k(D)\) to be zero. The author of this paper mainly shows first that if \(D\) is an orientation of \(G\) such that the number of Eulerian subgraphs of \(D\) of an even size is not the same as that of an odd size, then \(\chi(G)\leq \Delta_k(D)+k\). Secondly, the author shows that for any orientation \(D\) of \(G\), \(\chi(G)\leq 2\Delta_k(D)+k\). In addition, the author also provides a relation between \(\Delta_k(D)\) and vertex partitions of a graph into degenerate subgraphs.