Article ID Journal Published Year Pages File Type
420108 Discrete Applied Mathematics 2011 7 Pages PDF
Abstract

Let G=(V,E)G=(V,E) be a graph. A tolerance representation of GG is a set I={Iv:v∈V}I={Iv:v∈V} of intervals and a set t={tv:v∈V}t={tv:v∈V} of nonnegative reals such that xy∈Exy∈E iff Ix∩Iy≠0̸Ix∩Iy≠0̸ and ‖Ix∩Iy‖≥min{tx,ty}‖Ix∩Iy‖≥min{tx,ty}; in this case GG is a tolerance graph. We refine this definition by saying that GG is a pp-tolerance graph if tv/|Iv|≤ptv/|Iv|≤p for all v∈Vv∈V.A Grundy coloring gg of GG is a proper coloring of VV with positive integers such that for every positive integer ii, if i

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,