Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

Cooperative guards in art galleries

The art gallery problem was originally posed by Victor Klee in 1973 as the question of determining the minimum number of guards sufficient to see every point of the interior of an n-vertex simple polygon. The guard is assumed to be a stationary point which can see any other point that can be connected to it by a line segment within the art gallery. The first result is due to Chvátal (1975), who proved that ⌊n/3⌋ guards are occasionally necessary and always sufficient to cover a polygon with n vertices....

Equitable coloring of Kneser graphs

Robert FidytekHanna FurmańczykPaweł Żyliński — 2009

Discussiones Mathematicae Graph Theory

The Kneser graph K(n,k) is the graph whose vertices correspond to k-element subsets of set {1,2,...,n} and two vertices are adjacent if and only if they represent disjoint subsets. In this paper we study the problem of equitable coloring of Kneser graphs, namely, we establish the equitable chromatic number for graphs K(n,2) and K(n,3). In addition, for sufficiently large n, a tight upper bound on equitable chromatic number of graph K(n,k) is given. Finally, the cases of K(2k,k) and K(2k+1,k) are...

Page 1

Download Results (CSV)