%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{url}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\def\UrlFont{\rmfamily}

\newtheorem{theorem}{Théorème}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\def\abs#1{\left| #1 \right|}
\def\paren#1{\left( #1 \right)}
\def\acc#1{\left\{ #1 \right\}}
\def\floor#1{\left\lfloor #1 \right\rfloor}
\def\ceil#1{\left\lceil #1 \right\rceil}
\def\cro#1{\left[ #1 \right]}
\def\angle#1{\left\langle #1 \right\rangle}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{F. Jacques et P. Ochem  : La complexité de la $3+1/m$-coloration des graphes $P_t$-free}
%

% Pour le sommaire
\addcontentsline{toc}{section}{F. Jacques et P. Ochem  : La complexité de la $3+1/m$-coloration des graphes $P_t$-free}
%

% Pour la liste des auteurs
\index{Jacques, F.}\index{Ochem, P.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Fabien Jacques}, LIRMM, Montpellier, {\tt fabien.jacques@lirmm.fr}\\
\indent
Pascal Ochem, LIRMM, Montpellier, {\tt pascal.ochem@lirmm.fr}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé
Nous nous intéressons à la complexité de la $k$-coloration des graphes $P_t$-free (i.e. sans chemins de longueur $t$ au sens induit).

\medskip

Pour $k \ge 5$, ce problème est polynomial pour $t=5$ et NP-complet pour $t=6$. \cite{CKLSS2010,S2016}

Pour $k = 4$, ce problème est polynomial pour $t=6$ et NP-complet pour $t=7$. \cite{CSZ2019,S2016}

Pour $k = 3$, ce problème est polynomial pour $t=7$ et pseudo-polynomial pour tout $t$.\cite{BCMSSZ2018,PPR2020}

\medskip

Ainsi pour tout $t \ge 7$, la coloration avec au moins quatre couleurs des graphes $P_t$-free est difficile mais semble plus facile avec trois couleurs.

En utilisant la coloration circulaire qui permet de définir des nombres chromatiques rationnels, nous cherchons à localiser plus précisément ce saut de complexité entre 3 et 4.

%Soit $q=\frac n d$ un nombre rationnel, la clique circulaire $K_q$ est le graphe ayant pour sommets $\acc{x_0,x_1,\cdots,x_{n-1}}$ tel que $x_u$ et $x_v$ sont adjacents si et seulement si $ d\le|u-v|\le n-d$.
%Le nombre chromatique circulaire $\chi_c(G)$ est le plus petit $q$ tel que $G$ admet un homomorphisme vers $K_q$. 

%Nous montrons le théorème suivant:

\begin{theorem}
Pour tout entier $m\ge2$ fixé, savoir si un graphe $P_{30}$-free a un nombre chromatique circulaire au plus $3+\frac1m$ est NP-complet.
\end{theorem}

\begin{thebibliography}{6}

\bibitem{BCMSSZ2018} F.~Bonomo, M.~Chudnovsky, P.~Maceli, O.~Schaudt, M.~Stein, and M.~Zhong.
Three-coloring and list three-coloring graphs without induced paths on seven vertices.
\emph{Combinatorica} {\bf 38(4)} (2018), 779--801.

\bibitem{CKLSS2010} H.~Ch\'inh, M.~Kam\'inski, V.~Lozin, J.~Sawada, and X.~Shu.
Deciding $k$-colorability of $P_5$-free graphs in polynomial time.
\emph{Algorithmica} {\bf 57(1)} (2010), 74--81.

\bibitem{CSZ2019} M.~Chudnovsky, S.~Spirkl, and M.~Zhong.
Four-coloring $P_6$-free graphs.
\emph{SODA 2019} 1239--1256.

\bibitem{S2016} S.~Huang.
Improved complexity results on $k$-coloring $P_t$-free graphs.
\emph{European Journal of Combinatorics} {\bf 51} (2016), 336--346.

\bibitem{PPR2020} M.~Pilipczuk, M.~Pilipczuk, and P.~Rzazewski.
Quasi-polynomial-time algorithm for Independent Set in $P_t$-free and $C_{>t}$-free graphs via shrinking the space of connecting subgraphs.
\arxiv{2009.13494}


\end{thebibliography}
\end{document}

\vfill
\end{document}


