CanaDAM 2015 University of Saskatchewan, June 1 - 4, 2015 www.cms.math.ca//2015
 français conference home canadam home

Structural properties of graphs I
[PDF]

SEYYED ALIASGHAR HOSSEINI, Simon Fraser University
Cubic Normal Graphs  [PDF]

In 1999, De Simone and K\"{o}rner conjectured that every graph without induced $C_5,C_7,\overline{C}_7$ contains a clique cover $\mathcal C$ and a stable set cover $\mathcal I$ such that every clique in $\mathcal C$ and every stable set in $\mathcal I$ have a vertex in common. This conjecture has roots in information theory and became known as the Normal Graph Conjecture. Here we prove it for all triangle-free subcubic graphs.

This is a joint work with Seyed Saeed Changiz Rezaei and Bojan Mohar.

EMILY MARSHALL, Louisiana State University
Excluding a large theta graph  [PDF]

We provide a complete characterization of graphs that do not contain a large $\theta_{a,b,c}$ graph as a topological minor. More specifically, we describe the structure of $\theta_{1,2,t}$-, $\theta_{2,2,t}$-, $\theta_{1,t,t}$-, and $\theta_{2,t,t}$-free graphs where $t$ is large. The main result is a characterization of $\theta_{t,t,t}$-free graphs for large $t$. The $3$-connected $\theta_{t,t,t}$-free graphs are graphs without long paths and graphs formed by $3$-summing graphs without a long path to certain planar graphs. The $2$-connected graphs are then built up in a similar fashion by summing graphs without long paths to certain planar graphs. This work is joint with Guoli Ding.

SEYED SAEED CHANGIZ REZAEI, Department of Mathematics, Simon Fraser University
Almost all regular graphs are normal  [PDF]

In 1999, De Simone and K\"{o}rner conjectured that every graph without induced $C_5,C_7,\overline{C}_7$ contains a clique cover $\mathcal C$ and a stable set cover $\mathcal I$ such that every clique in $\mathcal C$ and every stable set in $\mathcal I$ have a vertex in common. This conjecture has roots in information theory and became known as the Normal Graph Conjecture. We prove that all graphs of bounded maximum degree and sufficiently large odd girth are normal. For fixed $d$ we show that random $d$-regular graphs are a.a.s normal.

This is joint work with Seyyed Aliasghar Hosseini and Bojan Mohar.