On properly ordered coloring of vertices in a vertex-weighted graph

Shinya Fujita, Sergey Kitaev, Shizuka Sato, Li-Da Tong

Research output: Contribution to journalArticlepeer-review

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 vertex-weighted 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 Gallai-Hasse-Roy-Vitaver 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.

Original languageEnglish
Number of pages12
JournalOrder
Early online date22 Feb 2021
DOIs
Publication statusE-pub ahead of print - 22 Feb 2021

Keywords

  • vertex coloring
  • properly ordered coloring
  • vertex-weighted graph
  • Gallai-Hasse-Roy-Vitaver theorem

Fingerprint Dive into the research topics of 'On properly ordered coloring of vertices in a vertex-weighted graph'. Together they form a unique fingerprint.

Cite this