On properly ordered coloring of vertices in a vertexweighted graph
Fujita, Shinya and Kitaev, Sergey and Sato, Shizuka and Tong, LiDa (2021) On properly ordered coloring of vertices in a vertexweighted graph. Order. ISSN 01678094
Text (FujitaetalOrder2021Onproperlyorderedcoloringofverticesinavertexweighted)
Fujita_etal_Order_2021_On_properly_ordered_coloring_of_vertices_in_a_vertex_weighted.pdf Accepted Author Manuscript Restricted to Repository staff only until 21 January 2022. Download (317kB)  Request a copy from the Strathclyde author 
Abstract
We introduce the notion of a properly ordered coloring (POC) of a weighted graph, that generalizes the notion of vertex coloring of a graph. Under a POC, if xy is an edge, then the larger weighted vertex receives a larger color; in the case of equal weights of x and y, their colors must be different. In this paper, we shall initiate the study of this special coloring in graphs. For a graph G, we introduce the function f(G) which gives the maximum number of colors required by a POC over all weightings of G. We show that f(G) = ℓ(G), where ℓ(G) is the number of vertices of a longest path in G. Another function we introduce is χ POC(G; t) giving the minimum number of colors required over all weightings of G using t distinct weights. We show that the ratio of χ POC(G; t) − 1 to χ(G) − 1 can be bounded by t for any graph G; in fact, the result is shown by determining χ POC(G; t) when G is a complete multipartite graph. We also determine the minimum number of colors to give a POC on a vertexweighted graph in terms of the number of vertices of a longest directed path in an orientation of the underlying graph. This extends the so called GallaiHasseRoyVitaver theorem, a classical result concerning the relationship between the chromatic number of a graph G and the number of vertices of a longest directed path in an orientation of G.
ORCID iDs
Fujita, Shinya, Kitaev, Sergey ORCID: https://orcid.org/0000000333241647, Sato, Shizuka and Tong, LiDa;

Item type: Article ID code: 75253 Dates: DateEvent22 February 2021Published22 February 2021Published Online21 January 2021AcceptedKeywords: vertex coloring, properly ordered coloring, vertexweighted graph, GallaiHasseRoyVitaver theorem, Mathematics, Computational Theory and Mathematics, Algebra and Number Theory, Geometry and Topology Subjects: Science > Mathematics Department: Faculty of Science > Mathematics and Statistics Depositing user: Pure Administrator Date deposited: 02 Feb 2021 16:28 Last modified: 12 Mar 2021 04:08 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/75253