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

DOI10.1007/S11083-021-09554-7MaRDI QIDQ2665834zbMATH OpenOpenAlexFDO

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

Publication date 19 November 2021

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.08432, https://strathprints.strath.ac.uk/75253/

zbMATH Keywords

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

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

x y

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) = e l l (G)

, where

e l l (G)

is the number of vertices of a longest path in

G

. Another function we introduce is

c h i_{P O C} (G; t)

giving the minimum number of colors required over all weightings of

G

using

t

distinct weights. We show that the ratio of

c h i_{P O C} (G; t) - 1

to

c h i (G) - 1

can be bounded by

t

for any graph

G

; in fact, the result is shown by determining

c h i_{P O C} (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

.

Review text

In this paper, the authors introduce the notion of \textit{properly order coloring} of a weighted graph, or \textit{POC}, which generalizes the notion of vertex coloring of a graph. Let \((G,w)\) be a vertex-weighted graph with vertex set \(V(G)\), edge set \(E(G)\) and a weight function \(w: V(G)\rightarrow W\), where \(W\) is a set of positive integers. A vertex coloring \(c: V(G)\rightarrow C\) on \((G,w)\), where \(C=\{1,2,\dots,\theta\}\), is a properly ordered coloring (POC) if for any edge \(uv\in E(G)\) the following conditions hold: \begin{itemize} \item if \(w(u)>w(v)\), then \(c(u)>c(v)\); \item if \(w(u)=w(v)\), then \(c(u)\ne c(v)\). \end{itemize} Then the authors define: \[ \chi_{POC}(G,w):=\min\{\theta\mid c\text{ is a POC on }(G,w)\} \] and \[ f(G):=\max\{\chi_{POC}(G,w)\mid w \text{ is a weight function on }G\}. \] Then, denoted by \(l(G)\) the number of vertices of a longest path in a graph \(G\), they prove the following: Theorem 1. Any graph \(G\) satisfies \(f(G)=l(G)\). The authors define also: \[ \chi_{POC}(G;t):=\min\{p\mid \chi_{POC}(G,w)\le p\text{ for every }w\text{ with }|W|=t\} \] and prove: Theorem 2. For a positive integer \(t\), any graph \(G\) satisfies \[ \dfrac{\chi_{POC}(G;t)-1}{\chi(G)-1}\le t. \] At last, given a digraph \(D\), let \(l'(D)\) be the number of vertices of a longest directed path in \(D\). The authors call an acyclic orientation for a vertex weighted graph \((G,w)\) \textit{good} if \(w(x)\ge w(y)\) holds for any arc \((x,y)\) in the orientation. Then, defined: \[ l'(G,w):=\min\{l'(D)\mid D\text{ is a good acyclic orientation on }(G,w) \] the authors prove the following: Theorem 3. Any weighted graph \((G,w)\) satisfies \(\chi_{POC}(G,w)=l'(G,w)\).

Recommendations

Cites work

Cited in

(1)

On an ordering problem in weighted hypergraphs

This page was built for publication: On properly ordered coloring of vertices in a vertex-weighted graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2665834)