UVictoria Discrete Math Seminar: Jing Huang

Strong cocomparability graphs are the reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows 01, 10. Strong cocomparability graphs form a subclass of cocomparability graphs (i.e., the complements of comparability graphs) and can be recognized in polynomial time.

In his seminal paper, Gallai characterized cocomparability graphs in terms of a forbidden structure called asteroids. Gallai proved that cocomparability graphs are precisely those reflexive graphs which do not contain asteroids.

In this talk, I will present a characterization of strong cocomparability graphs which is analogous to Gallai's characterization for cocomparability graphs. More precisely, I will show that strong cocomparability graphs are precisely those reflexive graphs which do not contain weak edge-asteroids (a weaker version of asteroids). The characterization also leads to a polynomial time recognition algorithm for strong cocomparability graphs.