Ordered colourings (Q1896351)

An ordered \(k\)-coloring of a graph \(G\) is a coloring function \(c: V(G)\to \{1, 2,\dots, k\}\) such that, for every pair of distinct vertices \(x\) and \(y\) and for every \(x\)-\(y\) path \(P\), if \(c(x)= c(y)\), then there exists an internal vertex \(z\) of \(P\) such that \(c(x)< c(z)\). This paper proves some results about ordered colorings of trees and planar graphs. For example, if every planar graph has an ordered coloring using at least \(g(v)\) vertices, then \(g(v)\leq 3(\sqrt 6+ 2)\sqrt v\). The paper also examines the relationship between connectivity and ordered colorings.