Skip to main content
All modules

TemplateJournalsmath

Electronic Journal of Combinatorics (e-jc)

Electronic Journal of Combinatorics paper on the official e-jc style, with the journal's theorem environments, MSC line and dateline in place.

Not stated in the file (distributed freely by the journal for author use)

Loading PDF preview…

What’s inside

  • Starter files
  • main.tex4.0 KB
    %% Electronic Journal of Combinatorics. e-jc.sty sits on top of article and
%% already defines theorem, lemma, corollary, proposition, definition,
%% example, conjecture, question, ... and loads amsthm, amssymb, hyperref.
\documentclass[12pt]{article}
\usepackage[amsmath,cleveref]{e-jc}
\usepackage{graphicx}
\usepackage{booktabs}
\usepackage{tikz}

\dateline{Month DD, YYYY}{TBD}{TBD}
\MSC{05C15, 05D40}
\Copyright{The authors. Released under the CC BY-ND license (International 4.0).}

\title{A Probabilistic Bound on the Chromatic Number\\ of Sparse Graphs}

\author{First Author\authornote{1}
\and
Second Author\authornote{2}
\and
Third Author\authornote{1,2}
}

\authortext{1}{Department of Mathematics, University Name, City, Country
  (\email{first@university.edu}, \email{third@university.edu}).}
\authortext{2}{Institute Name, City, Country (\email{second@institute.org}).}

\newcommand{\chr}{\chi}
\newcommand{\Gnp}{G(n,p)}

\begin{document}
\maketitle

\begin{abstract}
We show that a graph with maximum degree $\Delta$ and no triangles has
chromatic number $O(\Delta / \log \Delta)$, with an explicit constant,
by a short application of the Lov\'asz Local Lemma. The bound is tight up
to the constant for the random graph $\Gnp$.
\end{abstract}

\section{Introduction}

Bounding the chromatic number of triangle-free graphs in terms of the
maximum degree goes back to Johansson; see \cite{MolloyReed} for the
probabilistic background and \cite{Molloy2019} for the current best
constant. We give a streamlined argument for the following.

\begin{theorem}\label{thm:main}
There is a constant $C$ such that every triangle-free graph with maximum
degree $\Delta \ge 2$ satisfies $\chr(G) \le C\, \Delta / \log \Delta$.
\end{theorem}

\section{Preliminaries}

\begin{definition}
A \emph{proper colouring} of $G$ with $k$ colours is a map
$c \colon V(G) \to [k]$ with $c(u) \ne c(v)$ for every edge $uv$. The
\emph{chromatic number} $\chr(G)$ is the least such $k$.
\end{definition}

\begin{lemma}[Local Lemma, symmetric form]\label{lem:lll}
Let $A_1, \dots, A_m$ be events, each with probability at most $p$ and
each mutually independent of all but at most $d$ others. If
$e p (d+1) \le 1$ then with positive probability no $A_i$ occurs.
\end{lemma}

\section{Proof of \cref{thm:main}}

\begin{proof}
Colour every vertex independently and uniformly from $[k]$ with
$k = \lceil C \Delta / \log \Delta \rceil$, then uncolour every vertex that
shares its colour with a neighbour. For each vertex $v$ let $A_v$ be the
event that fewer than $\log \Delta / 10$ colours are available at $v$ after
this step. A Chernoff bound gives $\Pr[A_v] \le \Delta^{-3}$, and $A_v$
depends only on the colours at distance at most $2$, so $d \le \Delta^2$.
\cref{lem:lll} yields an outcome avoiding all $A_v$, and the remaining
vertices are then coloured greedily from their available lists.
\end{proof}

\begin{conjecture}
The optimal constant in \cref{thm:main} is $C = 1 + o(1)$.
\end{conjecture}

\cref{fig:sparse} shows a triangle-free graph attaining the bound up to the
constant, and \cref{tab:constants} compares known values of $C$.

\begin{figure}[ht]
\centering
\begin{tikzpicture}[every node/.style={circle,fill=black,inner sep=1.5pt}]
  \foreach \i in {0,...,6} {
    \node (a\i) at ({90+360/7*\i}:1.4cm) {};
  }
  \foreach \i in {0,...,6} {
    \pgfmathtruncatemacro{\j}{mod(\i+2,7)}
    \draw (a\i) -- (a\j);
  }
\end{tikzpicture}
\caption{The circulant graph $C_7(2)$: triangle-free with chromatic number $3$.}
\label{fig:sparse}
\end{figure}

\begin{table}[ht]
\centering
\begin{tabular}{@{}lcc@{}}
\toprule
Reference & Constant $C$ & Method \\
\midrule
Johansson (1996) & $9$ & semi-random colouring \\
Molloy \cite{Molloy2019} & $1 + o(1)$ & entropy compression \\
This paper & explicit & local lemma \\
\bottomrule
\end{tabular}
\caption{Constants in the bound $\chr(G) \le C \Delta / \log \Delta$.}
\label{tab:constants}
\end{table}

\section*{Acknowledgements}
We thank the referees for their careful reading.

\bibliographystyle{abbrv}
\bibliography{references}

\end{document}
  • Libraries and docs
  • e-jc.sty8.1 KBVendored from www.combinatorics.org on 2026-08-19.
    %% Style file for the Electronic Journal of Combinatorics
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{e-jc}[2023/07/03 Electronic Journal of Combinatorics]

% We change the footnote style to alphabetic in this style file
% for use in the author list.  Then it is changed back to numeric
% by \maketitle

\renewcommand{\thefootnote}{\textit{\alph{footnote}}}
\renewcommand{\thanks}[1]{\textbf{Please don't use ``thanks''.}}

\def\get@fnmark#1{%
  \begingroup
     \c@footnote #1\relax
     \unrestored@protected@xdef\@thisfnmark{\thefootnote}%
  \endgroup
  \@thisfnmark}
\def\authornote#1{\unskip\kern0.03em\proc@anote#1,,,,\endproc@anote}
\def\proc@anote#1,#2,#3,#4,#5\endproc@anote
{\def\@anoteA{\get@fnmark{#1}}%
  \ifx\relax#2\relax\let\@anoteB=\relax\else\def\@anoteB{,\get@fnmark{#2}}\fi
  \ifx\relax#3\relax\let\@anoteC=\relax\else\def\@anoteC{,\get@fnmark{#3}}\fi
  \ifx\relax#4\relax\let\@anoteD=\relax\else\def\@anoteD{,\get@fnmark{#4}}\fi
  \rlap{\@textsuperscript{\normalfont\@anoteA\@anoteB\@anoteC\@anoteD}}}
% \authortext accepts for its first argument either a number or {} or { }.
% The last two cases and number 0 create a footnote with an empty label.
\long\def\the@authortext{}
\long\def\authortext#1#2{%
  \ifx\relax#1\relax
  \g@addto@macro\the@authortext{\footnotetext[0]{\raggedright #2}}\else
  \ifx#1 % intentional space before percent
  \g@addto@macro\the@authortext{\footnotetext[0]{\raggedright #2}}\else
  \g@addto@macro\the@authortext{\footnotetext[#1]{\raggedright #2}}\fi\fi}

\newcommand\email[1]{\texttt{#1}}

% Use hanging indentation in footnotes
\long\def\@makefntext#1{\parindent 1.02em\noindent
   \everypar={\hangindent=1.02em}\hangindent=1.02em
  \hb@xt@1em{\hss\@textsuperscript{\normalfont\@thefnmark}}\kern0.02em #1}

\renewcommand\maketitle{\par
  \begingroup
    \def\@makefnmark{\rlap{\@textsuperscript{\normalfont\@thefnmark}}}%
    \newpage
    \global\@topnum\z@   % Prevents figures from going at top of page.
    \the@authortext
    \@maketitle
    \thispagestyle{plain} % \@thanks
  \endgroup
  \setcounter{footnote}{0}%
  \renewcommand{\thefootnote}{\arabic{footnote}}
  \global\let\maketitle\relax
  \global\let\@maketitle\relax
  \global\let\@author\@empty
  \global\let\@date\@empty
  \global\let\@title\@empty
  \global\let\title\relax
  \global\let\author\relax
  \global\let\date\relax
  \global\let\and\relax}

\DeclareOption{amsmath}{\let\use@amsmath=\relax}
\DeclareOption{cleveref}{\let\use@cleveref=\relax}
\ProcessOptions\relax

\RequirePackage[a4paper]{geometry}
\ifx\use@amsmath\undefined\else\RequirePackage{amsmath}\fi
\RequirePackage{amsthm,amssymb}
\RequirePackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\setlength{\textwidth}{160mm}
\setlength{\textheight}{221mm}
\setlength{\topmargin}{0pt}
\setlength{\headsep}{0pt}
\setlength{\headheight}{0pt}
\setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}
\setlength{\footskip}{9mm}

\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\le}{\leqslant}

\newenvironment{corrigendum}[1]%
{\clearpage\newpage\section*{Corrigendum -- submitted #1}}{}
\newenvironment{addendum}[1]%
{\clearpage\newpage\section*{Addendum -- submitted #1}}{}

\newcommand{\reusenumber}[2]{\setcounter{#1}{#2}\addtocounter{#1}{-1}}

\newcommand{\specs}[4]{\def\papno{#1}\def\volno{#2}\def\volyear{#3}\def\papid{#4}}
\ifx\volno\undefined\def\volno{30}\fi
\ifx\volyear\undefined\def\volyear{2023}\fi
\ifx\papno\undefined\def\papno{P00}\fi
\ifx\papid\undefined\def\papid{00000}\fi

\def\copy@right{PLEASE ADD A \texttt{\textbackslash Copyright\{\}} STATEMENT.}
\newcommand{\Copyright}[1]{\def\copy@right{\copyright\thinspace\ignorespaces#1}}
\newcommand{\dateline}[3]{\def\the@dateline{Submitted: \ignorespaces#1;
    Accepted: \ignorespaces#2; Published: \ignorespaces#3\\[0.5ex]\copy@right}}
\newcommand{\MSC}[1]{\def\the@MSC{\ignorespaces#1}}

\let\old@maketitle\maketitle
\renewcommand{\maketitle}{\date{\small\the@dateline}\old@maketitle}

\renewenvironment{abstract}{%
  \small
      \begin{center}%
	{\bfseries \abstractname\vspace{-.5em}\vspace{\z@}}%
      \end{center}%
      \quotation}%
  {\par\smallskip\noindent
   \textbf{Mathematics Subject Classifications: }\the@MSC\endquotation} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% The next group of commands makes the font smaller for the title and
%% for section and subsection headings, and adjusts the space just below 
%% each such heading.

\renewcommand\title[1]{\gdef\@title{\reset@font\Large\bfseries #1}}
\renewcommand\section{\@startsection {section}{1}{\z@}%
                                   {-3.5ex \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\normalfont\large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
                                     {-3ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
                                     {-2.5ex\@plus -1ex \@minus -.2ex}%
                                     {1.5ex \@plus .2ex}%
                                     {\normalfont\normalsize\bfseries}}

\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
                                     {2ex \@plus.5ex \@minus.2ex}%
                                     {-1em}%
                                     {\normalfont\normalsize\bfseries}}

\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
                                     {2ex \@plus.5ex \@minus .2ex}%
                                     {-1em}%
                                     {\normalfont\normalsize\bfseries}}

% These font declarations are for the footer appearing on all pages.
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
\newfont{\foottt}{cmtt10 at 10truept}

\renewcommand{\ps@plain}{%
\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics
{\footbf\volno} (\volyear), \#\papno\hfil
\ifnum\value{page}>1{\thepage}\else
 \href{https://doi.org/10.37236/\papid}{\foottt
      https://doi.org/10.37236/\papid\kern0.1em}\fi}}

\pagestyle{plain}
\g@addto@macro\bfseries{\boldmath}

%%%  Squashing the bibliography together a bit
  \newlength{\BiblioSpacing}
  \setlength{\BiblioSpacing}{0.4ex plus 0.1ex minus 0.1ex}
  \newcommand{\SquashBibFurther}{%
     \setlength{\BiblioSpacing}{0.2ex plus 0.1ex}}

  \let\oldthebibliography\thebibliography
  \let\endoldthebibliography\endthebibliography
  \renewenvironment{thebibliography}[1]{%
    \begin{oldthebibliography}{#1}%
      \setlength{\parskip}{\BiblioSpacing}
      \setlength{\itemsep}{\BiblioSpacing}
      \ifdefined\bibsep\setlength{\bibsep}{\BiblioSpacing}\fi% for natbib
  }%
  {%
    \end{oldthebibliography}%
  }

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

\ifx\use@cleveref\undefined
\else
  \ifx\cleverefoptions\undefined
      \RequirePackage{cleveref}%
  \else
      \RequirePackage[\cleverefoptions]{cleveref}%
  \fi
\fi

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

% For linking to an arXiv article:
\newcommand{\arxiv}[1]{\href{https://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% Typeset a doi. Some magic to make underscores work:
\def\doi{\begingroup\catcode`\_=12\relax\doi@arg}
\def\doi@arg#1{\href{https://doi.org/#1}{\texttt{doi:#1}}\endgroup}
  • references.bib821 B
    @book{MolloyReed,
  author    = {Molloy, Michael and Reed, Bruce},
  title     = {Graph Colouring and the Probabilistic Method},
  series    = {Algorithms and Combinatorics},
  volume    = {23},
  publisher = {Springer},
  address   = {Berlin},
  year      = {2002}
}

@article{Molloy2019,
  author  = {Molloy, Michael},
  title   = {The list chromatic number of graphs with small clique number},
  journal = {J. Combin. Theory Ser. B},
  volume  = {134},
  pages   = {264--284},
  year    = {2019}
}

@article{ErdosLovasz,
  author    = {Erd\H{o}s, Paul and Lov\'asz, L\'aszl\'o},
  title     = {Problems and results on 3-chromatic hypergraphs and some related questions},
  journal   = {Infinite and Finite Sets (Colloq. Math. Soc. J\'anos Bolyai)},
  volume    = {10},
  pages     = {609--627},
  year      = {1975}
}
  • main.pdfprebuilt · 196 KBReplaced by the first recompile.

    Binary file, seeded as-is.

  • main.synctex.gzprebuilt · 13 KBReplaced by the first recompile.

    Binary file, seeded as-is.