%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}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Circular $(4-\epsilon)$-coloring of some classes of signed graphs}
%

% Pour le sommaire
\addcontentsline{toc}{section}{Circular $(4-\epsilon)$-coloring of some classes of signed graphs}
%

% Pour la liste des auteurs
\index{Kardo\v{s}, F.}\index{Narboni, J.}\index{Naserasr, R.}\index{Wang, Z.}
%

% Citer un par un les auteurs et leur affiliation
Franti\v{s}ek Kardo\v{s}, LaBRI, Bordeaux and Comenius University, Bratislava, Slovakia, {\tt frantisek.kardos@u-bordeaux.fr}\\
\indent
Jonathan Narboni, LaBRI, Bordeaux, {\tt jonathan.narboni@u-bordeaux.fr}\\
\indent
Reza Naserasr, IRIF, Paris, {\tt reza@irif.fr}\\
\indent
\underline{Zhouningxin Wang}, IRIF, Paris, {\tt wangzhou4@irif.fr}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

A circular $r$-coloring of a signed graph $(G, \sigma)$ is an assignment $\phi$ of points of a circle $C_r$ of circumference $r$ to the vertices of $(G, \sigma)$ such that for each positive edge $uv$ of $(G, \sigma)$ the distance of $\phi(v)$ and $\phi(v)$ is at least 1 and for each negative edge $uv$ the distance of $\phi(u)$ from the antipodal of $\phi(v)$ is at least 1. The circular chromatic number of $(G, \sigma)$, denoted $\chi_c(G, \sigma)$, is the infimum of all $r$ such that $(G, \sigma)$ admits a circular $r$-coloring. 

This notion is recently defined by Naserasr, Wang, and Zhu. Among other results, they proved that for any signed $d$-degenerate simple graph $\hat{G}$, $\chi_c(\hat{G})\leq 2d$. For $d\geq 3$, examples of signed $d$-degenerate simple graphs of circular chromatic number $2d$ are provided. But for $d=2$ only examples of signed 2-degenerate simple graphs of circular chromatic number close enough to $4$ are given, noting that these examples are also signed bipartite planar graphs. Using the notion of circular coloring and via a graph operation, we observe that the celebrated 4-Color Theorem could be restated as follows: If $(G,\sigma)$ is a signed bipartite planar simple graph where vertices of one part are all of degree $2$, then $\chi_c(G,\sigma)\leq \frac{16}{5}$. 


Motivated from above, the classes of signed $2$-degenerate simple graphs and signed bipartite planar simple graphs are of special interest in this study. We provide an improved upper bound of $4-\frac{2}{\lfloor \frac{n+1}{2} \rfloor}$ for the circular chromatic number of a signed 2-degenerate simple graph on $n$ vertices and an improved upper bound of $4-\frac{4}{\lfloor \frac{n+2}{2} \rfloor}$ for the circular chromatic number of a signed bipartite planar simple graph on $n$ vertices. We then show that each of the bounds is tight for any value of $n\geq 2$.

%Veillez Ã  ce que le rÃ©sumÃ© n'excÃ¨de pas {\bf 1 page}, en ne modifiant
%ni la taille de la police, ni les marges, ni l'Ã©cart entre les
%  lignes, ni l'Ã©cart entre les mots, ni l'Ã©cart entre les
%  lettres\footnote{et en Ã©vitant de mettre des notes de bas de page
%    pour caser plus de texte ni vu ni connu!}.
%
%\smallskip
%
%Si vous souhaitez ajouter une figure, faites-en sorte qu'elle soit
%compilable par {\tt pdflatex} (pas de {\tt pstricks} ou d'{\tt eps}). Vous pouvez aussi
%utiliser tikz si vous le souhaitez.
%
%\smallskip
%
%
%Vous pouvez Ã©galement ajouter des rÃ©fÃ©rences, comme~\cite{nk1} ci-dessous.
%
%
%
%\begin{thebibliography}{99}
%
%\bibitem{nk1}
%N.~Trotignon and K.~Vu{\v s}kovi{\'c}, \emph{A structure theorem for graphs with no cycle with a unique chord and
%  its consequences}, J. Graph Theory {\bf 63(1)} (2010), 31--67.
%
%\end{thebibliography}


\vfill
\end{document}








