%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{amsthm,amsmath}
\newcommand{\chid}{\chi'^d_{\sum}}
\newtheorem{conjecture}{Conjecture}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{A. Dailly, E. Duchêne, A. Parreau et E. Sidorowicz :\\La coloration $d$-relaxée somme-distinguante}
%

% Pour le sommaire
\addcontentsline{toc}{section}{A. Dailly, E. Duchêne, A. Parreau et E. Sidorowicz : La coloration $d$-relaxée somme-distinguante}
%

% Pour la liste des auteurs
%

% Citer un par un les auteurs et leur affiliation
\underline{Antoine Dailly}, G-SCOP, Grenoble, {\tt antoine.dailly@grenoble-inp.fr}\\
\indent
Éric Duchêne, LIRIS, Lyon, {\tt eric.duchene@univ-lyon1.fr}\\ %souligner l'orateur
\indent
Aline Parreau, LIRIS, Lyon {\tt aline.parreau@univ-lyon1.fr}\\
\indent
El\.zbieta Sidorowicz, University of Zielona Góra, Pologne {\tt e.sidorowicz@wmie.uz.zgora.pl}\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

Une $k$-coloration des arêtes d'un graphe connexe $G(V,E)$ est une fonction $\omega:E \rightarrow \{1,\ldots,k\}$. Une coloration des arêtes $\omega$ induit à son tour une coloration des sommets $\sigma_\omega$ où chaque sommet est coloré par la somme des couleurs de ses arêtes incidentes : $\sigma_\omega(u) = \sum_{v \in N(u)} \omega(uv)$. Une coloration des arêtes $\omega$ est appelée \emph{somme-distinguante} si la coloration des sommets $\sigma_\omega$ qu'elle induit est propre, c'est-à-dire si, pour toute arête $uv$, $\sigma_\omega(u) \neq \sigma_\omega(v)$. Tout graphe différent de $K_2$ admet une telle coloration.

Deux types de colorations d'arêtes somme-distinguantes ont été particulièrement étudiés : les colorations propres et impropres. Le cas impropre a donné lieu à la fameuse Conjecture 1-2-3~\cite{KaLu04}, qui affirme que tout graphe admet une 3-coloration impropre de ses arêtes somme-distinguante ; le cas propre a une conjecture similaire affirmant que tout graphe (sauf $C_5$) admet une $(\Delta(G)+2)$-coloration propre de ses arêtes domme-distinguante~\cite{FlMa13}.

Nous généralisons ces deux conjectures, en introduisant la \emph{$k$-coloration d'arêtes $d$-relaxée somme-distinguante} : il s'agit d'une $k$-coloration d'arêtes somme distinguante dans laquelle chaque sommet est incident à au plus $d$ arêtes de la même couleur. Le plus petit $k$ tel qu'une telle coloration de $G$ existe est noté $\chid(G)$. Nous proposons donc la conjecture généralisée suivante :

\begin{conjecture}
	Pour tout $G \neq C_5$ connexe, $\chid(G) \leq \left\lceil \frac{\Delta(G)}{d} \right\rceil + 2$.
\end{conjecture}

Nous démontrons cette conjecture pour les arbres, les graphes complets dans les cas $d=2$ et $d \in \{\lceil\frac{n-1}{2}\rceil,\ldots,n-1\}$ et les graphes subcubiques dans le cas $d=2$. Nous déterminons également la valeur exacte de $\chid$ pour les graphes complets dans le cas $d=2$ et pour les arbres.

\begin{thebibliography}{99}

\bibitem{FlMa13}  Flandrin, E.,  Marczyk, A.,  Przyby{\l}o, J.,  Sacle, J-F.,   Wo\'zniak, M. (2013). Neighbour sum distinguishing index. \emph{Graphs Combin.} \textbf{29}(5), 1329--1336.

\bibitem{KaLu04}  Karo\'nski, M.,  {\L}uczak, T.,  Thomason, A. (2004).  Edge weights and vertex colours. \emph{J. Combin. Theory Ser. B} \textbf{91}, 151--157.

\end{thebibliography}


\vfill
\end{document}
