\documentclass[11pt]{article}
\usepackage[russian,greek,english]{babel}
\usepackage{amsmath,ifthen,color,eurosym}
\usepackage{wrapfig,hyperref,cite}
\usepackage{latexsym,amsthm,amsmath,amssymb,url,cite}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{stmaryrd,wasysym}
\usepackage{colortbl}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}

\def\baselinestretch{1}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{observation}{Observation}
\newtheorem{proposition}{Proposition}

\setlength{\textheight}{22cm}
\setlength{\topmargin}{-1cm}
\setlength{\textwidth}{165mm}
\setlength{\oddsidemargin}{-3mm}
\setlength{\unitlength}{1mm}


%\renewcommand{\refname}{\small References}
\addto{\captionsenglish}{\renewcommand{\refname}{\normalsize
    References}}



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
%Put here the package you need, new commands, ...



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%

\begin{document}
%1 page max !! 

%Write your title here: 
\noindent{\bf\Large Colouring graphs with constraints on local connectivity}

%List the authors as follows (you may underline the speaker, or just
%name the speaker, and mention your co-authors at the end, up to you):  
\noindent P. Aboulker -- {\small Universidad Andres Bello, Santiago, Chile} \\
\noindent \underline{N.  Brettell} -- {\small Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI)} \\
\noindent F. Havet -- {\small Project Coati, I3S (CNRS, UNS) and INRIA, Sophia Antipolis, France} \\
\noindent D. Marx -- {\small Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI)} \\
\noindent N. Trotignon -- {\small LIP, ENS Lyon}



\vspace{2ex}

\noindent{\bf Abstract:} %Here write your abstract

It is well known that deciding if a graph has a proper vertex $k$-colouring is NP-complete for any fixed $k$ at least $3$.  On the other hand, if we restrict our attention to graphs with maximum degree at most $k$, Brooks' theorem implies that it is easy to find a $k$-colouring, or determine that none exists, in polynomial time.  In this talk, we consider several generalisations of the class of graphs with maximum degree at most $k$ --- each defined by constraining the local connectivity of some, or all, pairs of vertices --- and consider the complexity of $k$-colouring for graphs in these classes.

A graph has \emph{maximal local connectivity~$k$} (respectively, \emph{maximal local edge-connectivity~$k$}) if no pair of distinct vertices have more than $k$ internally disjoint (respectively, edge-disjoint) paths between them.
We characterise the $3$-colourable graphs with maximal local edge-connectivity~$3$, the $3$-colourable $3$-connected graphs with maximal local connectivity~$3$, and the $k$-colourable $k$-connected graphs with maximal local edge-connectivity~$k$.
It follows that there is a polynomial-time algorithm that, for a graph in one of these classes, finds a $3$- or $k$- colouring, or determines that none exists.
On the other hand, deciding the $k$-colourability of minimally $k$-connected graphs, or deciding the $3$-colourability of $(k-1)$-connected graphs with maximal local connectivity~$k$, is shown to be NP-complete.

%If you need a ref section, do it more or less like that : 
%\small
%\begin{thebibliography}{1}

%\bibitem{CCHPP}
%R.~H. Chitnis, M.~Cygan, M.~Hajiaghayi, M.~Pilipczuk, and M.~Pilipczuk.
%\newblock Designing {FPT} algorithms for cut problems using randomized
  %contractions.
%\newblock In {\em 53rd Annual {IEEE} Symposium on Foundations of Computer
  %Science (FOCS)}, pages 460--469, 2012.

%\bibitem{Wol15}
%P.~Wollan.
%\newblock The structure of graphs not admitting a fixed immersion.
%\newblock {\em Journal of Combinatorial Theory, Series {B}}, 110:47--66, 2015.

%\end{thebibliography}


\end{document}
