Cooperatie guards in the fortress problem.
Orthogonal art galleries with holes: a coloring proof of Aggarwal's theorem.
Cooperative guards in art galleries with one hole.
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
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