[Discrete-math-seminar] Reminder: 12:45 seminar in E1 123

Michael Pelsmajer pelsmajer at iit.edu
Tue Mar 31 19:22:36 CDT 2009


Reminder: There's an unusual time and location for the special joint
seminar tomorrow.

Please join us tomorrow for a special Joint Seminar, co-sponsored by
the Applied Mathematics Department and the Math Club.  Please note the
special time, location, and comestibles.

Wednesday, April 1,
12:50-1:40pm (pizza at 12:45)
E1 123

Two IIT undergraduate students will present original research!  Each
talk will be 20 minutes, plus a few minutes for questions - which is a
tight schedule, so please, don't be late.

-------------------------------------------------

Orthogonal Art Gallery with Holes
YoungJu Jo, Illinois Institute of Technology

The original art gallery problem (V.Klee, 1973) asked for the minimum
number of guards sufficient to see every point of the interior of an
n-vertex simple polygon. Chvatal (1975) proved that n/3 guards are
always sufficient. If all the edges of the given simple polygon are
either horizontal or vertical, then such a polygon is called an
orthogonal polygon. Kahn, Klawe and Kleitman (1983) proved that n/4
guards are sufficient for such a n-vertex gallery.

We are interested in orthogonal gallery with holes, i.e, an orthogonal
polygon enclosing some other orthogonal polygons called holes such
that interior of each hole is empty (these are obstructions to
visibility). In 1982, Shermer conjectured that any orthogonal polygon
with n vertices and h holes can be guarded by (n+h)/4 guards. This
conjecture remains open. The best known result shows that (n+2h)/4
guards suffice (O'Rourke 1987). In this talk we will discuss the
history of these problems and some of the proofs. We will outline our
approach to proving that (n+(5/3)h)/4 guards suffice for an orthogonal
gallery with n vertices with h holes. This is joint work with Prof
Hemanshu Kaul.

--------------------------------------------------

On Graph Fall-Coloring
Christos Mitillos, Illinois Institute of Technology

Graph coloring deals with the partition of the vertices of a graph
into sets, or color classes, of pairwise non-adjacent vertices. Graph
domination studies sets of vertices which are within a distance of 1
from all vertices. Both concepts are often applied in real life
scheduling and location problems on networks. We are interested in a
common extension of both these concepts.

Fall coloring of graphs, introduced by Dunbar et al. (2000) asks for a
partition of the vertices of a graph into color classes, each of which
is also a dominating set. We study the question: When does a graph
have a fall-coloring?

Our results include characterization of fall-colorable threshold
graphs and fall-colorable split graphs. We also study the
fall-coloring of cartesian products of graphs and interval graphs.
Finally, we construct a family of graphs which can be only
fall-colored using predetermined, non-consecutive number of colors.
This is joint work with Prof Hemanshu Kaul.

--------------------------------------------------



Michael J. Pelsmajer             http://www.iit.edu/~pelsmaje
Applied Mathematics, E1 Room 206       pelsmajer at iit.edu
Illinois Institute of Technology         (312)567-5344
Chicago, IL 60616


More information about the Discrete-math-seminar mailing list