%Compiler avec pdflatex, le résultat ne doit pas dépasser une page
%Merci de respecter scrupuleusement ce modèle.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{mathrsfs}
%\usepackage {xcolor}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\usepackage{float}
\usepackage{graphics}
\usepackage{url}
\usepackage{pdfpages}

\DeclareMathOperator{\free}{Free}
\newtheorem{theorem}{Theorem}


\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{C. Robin : When all holes have the same length}
%

% Pour le sommaire
\addcontentsline{toc}{section}{C. Robin : When all holes have the same length}
%

% Pour la liste des auteurs
\index{Robin, C.}
%

% Citer un par un les auteurs et leur affiliation
Jake Horsfield, University of Leeds, U.K., {\tt sc15jh@leeds.ac.uk}\\
\indent
Myriam Preissmann, G-Scop, Grenoble, {\tt myriam.preissmann@grenoble-inp.fr}\\
\indent
\underline{Cléophée Robin}, G-Scop, Grenoble, {\tt cleophee.robin@grenoble-inp.fr}\\ %souligner l'orateur
\indent 
Nicolas Trotignon, LIP, Lyon, {\tt nicolas.trotignon@ens-lyon.fr  }\\
\indent 
Ni Luh Dewi Sintiari, LIP, Lyon {\tt ni-luh-dewi.sintiari@ens-lyon.fr}\\
\indent 
Kristina Vu\v{s}kovi\'{c}, University of Leeds, U.K., {\tt K.Vuskovic@leeds.ac.uk   }\\


A \emph{hole} is an induced cycle of length at least 4. For an integer $k\geq 4$, we denote by $\mathcal C_k$, the class  of graphs where every hole has length $k$.

We have defined a new class of graphs named \emph{blowup of $\ell$-templatse} whose all holes have length $2\ell +1$. Using earlier results on other related classes of graphs, we did obtain the following structural theorem :

\begin{theorem}
Let $\ell \ge 3$ be an integer.  If $G$ is a graph in $\mathcal C_{2\ell +1}$ then
  one of the following holds:
  \begin{itemize}
  \item $G$ is a ring of length $2\ell+1$ (\cite{1}),
  \item $G$ is a proper blowup of a twinless odd $\ell$-template, 
  \item $G$ has a universal vertex,
  \item $G$ has a clique cutset.
  \end{itemize}
  
\end{theorem}


The classes of perfect graphs (\cite{2}) and even-hole-free graphs (\cite{3}), both exclude holes depending on the parity of their length. For an even $k\geq 6$, $\mathcal C_k$ is a subclass of the class of perfect graphs and for an odd $k$, $\mathcal C_k$ is a subclass of even-hole-free graphs. The well known class of chordal graphs (graphs containing no hole) is trivially included in every $\mathcal C_k$



Linda Cook and Paul Seymour independently found a similar characterization.



\begin{thebibliography}{99}

\bibitem{1}

V.~Boncompagni, I.~Penev and K.~Vu{\v s}kovi{\'c}, \emph{Clique cutsets beyond chordal graphs}, Electronic Notes in Discrete Mathematics (2017), 62:81--86.

\bibitem{2}

M.~Chudnovsky, N.~Robertson, P.~Seymour and R.~Thomas, \emph{The strong perfect graph theorem}, Annals of Mathematics (2005), 164:51--229.


\bibitem{3}

K.~Vu{\v s}kovi{\'c}, \emph{Even-hole-free graphs: A survey}, Applicable Analysis and Discrete Mathematics (2010), 4. 

\end{thebibliography}

\vfill
\end{document}
