Events & News
Colloquium
| Category | Lecture |
| Date | Thursday, January 17, 2013 |
| Time | 11:00 am |
| Concludes | 12:15 pm |
| Location | Gould-Simpson 906 |
| Speaker | Steven Chaplick |
| Affiliation | University of Toronto |
Max-Point Tolerance Graphs
A graph G is max-point-tolerance (MPT) when each vertex v of G can be mapped to a pointed- interval (I_v, p_v ) where I_v is an interval of on the real line and point p_v ∈ I_v is such that
(u,v) is an edge of G if I u ∩ I v ⊇{p_u , p_v}; i.e., each pair of intervals can “tolerate” a non-empty intersection (without forming an edge) as long as both of their distinguished points are not contained in this intersection. MPT graphs arise naturally as a way to model relationships among DNA fragments in genome-wide association studies.
We formally introduce this graph class and provide characterizations of it. One characterization is geometric. Specifically, G is MPT if G is an intersection graph of L-shapes where the “corners” of the Ls form a line. Another is a four point vertex ordering condition; i.e., G is MPT if the vertices of G can be linearly ordered by < so that: no quadruple u , v , w , x ∈ V(G) with u < v < w < x has the edges (u,w), (v,x) without the edge (v,w). The last is that every MPT graph is the intersection of a special pair of interval graphs. We further demonstrate several connections to known graph classes; e.g., we show that the MPT graphs are a strict superset of interval graphs incomparable permutation, chordal, and planar graphs. Finally, we show that the weighted independent set problem can be solved in polynomial time on MPT graphs and that the coloring problem is NP-complete.