Resolving Stanley's $e$-positivity of claw-contractible-free graphs
Samantha Dahlberg
Ang\`{e
Stephanie van Willigenburg
In Stanley's seminal 1995 paper on the chromatic symmetric function, he stated that there was no known graph that was not contractible to the claw and whose chromatic symmetric function was not $e$-positive, namely, not a positive linear combination of elementary symmetric functions. We resolve this by giving infinite families of graphs that are not contractible to the claw and whose chromatic symmetric functions are not $e$-positive. Moreover, one such family is additionally claw-free, thus establishing that the $e$-positivity of chromatic symmetric functions in general is not dependent on the claw.
1703.05770.tex
% chrom paper 2
\documentclass[12pt]{amsart}  %[12pt] while developing, omitted for final
%\documentclass{amsart}  %used for final

%packages
\usepackage[latin1]{inputenc}
\usepackage{amsmath} 
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{latexsym} 
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{color}
\usepackage{hyperref}
\usepackage{verbatim}
\usepackage[all]{xy}
\usepackage{graphics}
\usepackage{pdfsync}
%\usepackage{natbib}
%\usepackage[notref, notcite]{showkeys} %shows labels
\usepackage{tikz}
\usetikzlibrary{fit,calc,positioning,decorations.pathreplacing,matrix}
\usepackage{url}



% 1in margins at left and right
\oddsidemargin=0in
\evensidemargin=0in
\textwidth=6.50in             % paper is 8.50in wide


% 1in margins at top and bottom
\headheight=10pt
\headsep=10pt
\topmargin=.5in
\textheight=8in

%% Theorem definitions
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{algorithm}[theorem]{Algorithm} 
\newtheorem{procedure}[theorem]{Procedure}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{case}{Case}
\newtheorem{xca}[theorem]{Exercise}

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


\numberwithin{equation}{section}
\renewcommand{\labelitemi}{$\circ$} % A typesetting pun?!
\setcounter{MaxMatrixCols}{20}

%\newcommand{\todo}[1]{\vspace{5 mm}\par \noindent
%\marginpar{\textsc{ToDo}}
%\framebox{\begin{minipage}[c]{0.95 \textwidth} #1 \end{minipage}}\vspace{5 mm}\par}

%%remove the comment from the following line to remove all the
%% 'to do' remarks:
%%\renewcommand{\todo}[1]{}

%\newcommand{\comment}[1]{\vspace{5 mm}\par \noindent
%\marginpar{\textsc{Comment}}
%\framebox{\begin{minipage}[c]{0.95 \textwidth}
% #1 \end{minipage}}\vspace{5 mm}\par}

%%remove the comment from the following line to remove all the
%% 'comment' remarks:
%%\renewcommand{\comment}[1]{}

%\newcommand{\new}[1]{\ensuremath{\blacktriangleright}#1\ensuremath{\blacktriangleleft}}


%%%%%%blackboard letters
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bK}{\mathbb{K}}
\newcommand{\bP}{\mathbb{Z}_+} 
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\suchthat}{\;|\;}
\newcommand{\spam}{\operatorname{span}}

%:graph definitions
\newcommand{\sa}{{SA}}
\newcommand{\san}{{SA}_{n,n}}
\newcommand{\as}{{AS}}
\newcommand{\aseven}{{AS}_{n,n}}
\newcommand{\asodd}{{AS}_{n,n+1}}
\newcommand{\trt}{{TT}}
\newcommand{\trtn}{{TT}_{n,n,n}}
\newcommand{\ccf}{claw-contractible-free}

%:Sym definitions
\newcommand{\Sym}{\ensuremath{\operatorname{Sym}}}

%: compositions and tableaux
\newcommand\ol[1]{\overline{#1}}
\newcommand\ul[1]{\underline{#1}}
\newcommand\ch[1]{\check{#1}}
\newcommand\strongof[1]{{#1}^+}
\newcommand\partitionof[1]{\widetilde{#1}}
\newcommand\reverse[1]{{#1}^*}
\newcommand\ccomplement[1]{{#1}^c}
\newcommand\ctranspose[1]{{#1}^t}
\newcommand{\coarsep}{\succcurlyeq _p}


%%% tableau macros %%%
\newlength\cellsize \setlength\cellsize{15\unitlength}
\savebox2{%
\begin{picture}(15,15)
\put(0,0){\line(1,0){15}}
\put(0,0){\line(0,1){15}}
\put(15,0){\line(0,1){15}}
\put(0,15){\line(1,0){15}}
\end{picture}}
\newcommand\cellify[1]{\def\thearg{#1}\def\nothing{}%
\ifx\thearg\nothing
\vrule width0pt height\cellsize depth0pt\else
\hbox to 0pt{\usebox2\hss}\fi%
\vbox to 15\unitlength{
\vss
\hbox to 15\unitlength{\hss$#1$\hss}
\vss}}
\newcommand\tableau[1]{\vtop{\let\\=\cr
\setlength\baselineskip{-16000pt}
\setlength\lineskiplimit{16000pt}
\setlength\lineskip{0pt}
\halign{&\cellify{##}\cr#1\crcr}}}
\savebox3{%
\begin{picture}(15,15)
\put(0,0){\line(1,0){15}}
\put(0,0){\line(0,1){15}}
\put(15,0){\line(0,1){15}}
\put(0,15){\line(1,0){15}}
\end{picture}}
\newcommand\expath[1]{%
\hbox to 0pt{\usebox3\hss}%
\vbox to 15\unitlength{
\vss
\hbox to 15\unitlength{\hss$#1$\hss}
\vss}}
\newcommand\bas[1]{\omit \vbox to \cellsize{ \vss \hbox to \cellsize{\hss$#1$\hss} \vss}}

\newcommand{\emt}{\mbox{ }}
\newcommand{\gst}{\bullet}
\newcommand{\ginf}{\gx{\small $\infty$}}


%%%%% end tableaux macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}
\title[$e$-positivity of claw-contractible-free graphs]{Resolving Stanley's $e$-positivity of claw-contractible-free graphs}

\author{Samantha Dahlberg}
\address{
Department of Mathematics,
 University of British Columbia,
 Vancouver BC V6T 1Z2, Canada}
\email{samadahl@math.ubc.ca}

\author{Ang\`{e}le Foley}
\address{
Department of Physics and Computer Science, 
Wilfrid Laurier University, 
Waterloo ON N2L 3C5, Canada}
\email{ahamel@wlu.ca}

\author{Stephanie van Willigenburg}
\address{
 Department of Mathematics,
 University of British Columbia,
 Vancouver BC V6T 1Z2, Canada}
\email{steph@math.ubc.ca}


%\thanks{
%All three authors were supported  in part by the National Sciences and Engineering Research Council of Canada.}
\subjclass[2010]{Primary 05E05; Secondary 05C15, 05C25, 06A11, 16T30, 20C30}
\keywords{chromatic symmetric function,  claw-free, claw contractible, elementary symmetric function}


\begin{abstract}
In Stanley's seminal 1995 paper on the chromatic symmetric function, he stated that there was no known graph that was not contractible to the claw and whose chromatic symmetric function was not $e$-positive, namely, not a positive linear combination of elementary symmetric functions. We resolve this by giving infinite families of graphs that are not contractible to the claw and whose chromatic symmetric functions are not $e$-positive. Moreover, one such family is additionally claw-free, thus establishing that the $e$-positivity of chromatic symmetric functions in general is not dependent on the claw.
\end{abstract}
\maketitle

%\tableofcontents

% Introduction
\section{Introduction}\label{sec:intro}
The chromatic polynomial is a classical graph invariant dating back to Birkhoff \cite{Birkhoff}, while symmetric functions date back even further to Cauchy \cite{Cauchy}, and their impact is still felt today in many areas  from algebraic geometry to quantum physics. In 1995 Stanley \cite{Stan95} integrated these two functions, introducing a natural symmetric function generalization of the chromatic polynomial for any finite simple graph, $G$, known as the chromatic symmetric function, $X_G$. This function has been an active area of research since then, with a marked increase in activity recently. One of the major avenues of research has been the further generalization and application of these functions. For example, Stanley \cite{Stan_AG} introduced symmetric function generalizations of the Tutte polynomial and the bad colouring polynomial, and generalized $X_G$ to hypergraphs. Meanwhile Noble and Welsh generalized to the $U$-polynomial \cite{Noble} and Brylawski to the polychromate \cite{Bryl}, which were proved to be equal by Sarmiento  \cite{Sarm}. 

Other generalizations to more geometric settings included to matroids by Billera \emph{et al.} \cite{BJR} and to simplicial complexes by Benedetti \emph{et al.} \cite{Benedetti}. 
%Rosas extended the chromatic symmetric function to MacMahon symmetric functions \cite{Rosas}, 
Meanwhile Gebhard and Sagan took this approach to noncommuting variables \cite{GebSag} where deletion-contraction is satisfied, whereas with  the chromatic symmetric function Orellana and Scott \cite{Orellana} showed that instead triple-deletion exists. However, the most substantial generalizations have been to quasisymmetric functions by Humpert \cite{Humpert}, but most notably by Shareshian and Wachs, for example \cite{SW}, whose refinement has been studied yet further by others, for example \cite{Ath, BrosnanC, Clearman}. Regarding applications, the chromatic symmetric function has also been applied to scheduling problems via a generalization of Breuer and Klivans \cite{BK}, and has been seen to distinguish various non-isomorphic trees, for example \cite{Jose2, MMW}, while the symmetric bad colouring polynomial arose in the study of the Potts model by Klazar et al. \cite{Klazar}.

Returning to the generalization by Shareshian and Wachs, one motivation was rooted in the desire to resolve the 1995 conjecture  of Stanley \cite[Conjecture 5.1]{Stan95} that if a poset is $(\mbox{\textbf{3}}+\mbox{\textbf{1}})$-free, then the chromatic symmetric function of its incomparability graph (which is thus claw-free) is a non-negative linear combination of elementary symmetric functions, that is, $e$-positive. This is equivalent to the Stanley-Stembridge poset chain conjecture from 1993 \cite{StanStem}.
%This conjecture arose after a conjecture of Goulden and Jackson regarding immanants of Jacobi-Trudi matrices \cite{GJ}, which was swiftly proved by Greene \cite{Greene}. However, this led to a further immanant conjecture by Stanley and Stembridge \cite{StanS}, which was equivalent to that given above. 
A variety of partial results have been obtained such as when the graph is a path or cycle \cite{Carlitz,  Stan95, Wolfe}, and particular coefficients were recently found by Paunov \cite{Paunov1, Paunov2}. Guay-Paquet \cite{GP} also showed that the conjecture can be reduced from $(\mbox{\textbf{3}}+\mbox{\textbf{1}})$-free posets to $(\mbox{\textbf{3}}+\mbox{\textbf{1}})$-free \emph{and} $(\mbox{\textbf{2}}+\mbox{\textbf{2}})$-free posets. 

Gasharov \cite{Gash} also proved a special case of the conjecture involving $2\times 2$ minors, which generalized a result of Krattenthaler \cite{Kratt}. However, Gasharov is best known for proving Stanley's conjecture when elementary symmetric functions are replaced by Schur functions \cite{Gasharov}, which has led to its own avenue of research, for example \cite{Kaliz, SWW}, since $e$-positivity implies Schur-positivity, both of which are central to representation theory.



The purpose of our paper is to resolve in the negative the related $e$-positivity statement of Stanley \cite[p 188]{Stan95}
\begin{quote} \emph{We don't know of a graph which is not contractible to $K_{13}$ (even regarding multiple edges of a contraction as a single edge) which is not $e$-positive.}
\end{quote}

More precisely, our paper is structured as follows. In Section~\ref{sec:background} we recall relevant concepts that we will require later, and give the four graphs with the fewest number of vertices that are not contractible to the claw and whose chromatic symmetric functions are not $e$-positive in Figure~\ref{fig:4counter}. Then in Section~\ref{sec:saltires} we  generalize two of these graphs into two infinite families of graphs. First is the family of saltire graphs, $\sa _{a,b}$, where $a,b\geq 2$, which generalizes the graph from the previous section with the fewest edges. We prove that these graphs are not contractible to the claw in Lemma~\ref{lem:sa_ccf}, and additionally for $n\geq 3$ we prove that $X_{\san}$ is not $e$-positive in Lemma~\ref{lem:sa_notepos}, together giving Theorem~\ref{the:sanotpositive}. 

Having discovered a family of graphs with an even number of vertices that resolves Stanley's statement we then extend our results to graphs with any number of vertices via the second family of augmented saltire graphs, $\as _{a,b}$, where $a\geq2, b\geq 3$, which we also prove are not contractible to the claw in Lemma~\ref{lem:as_ccf}. For $n\geq 3$   we further prove that $X_{\aseven}$ and $X_{\asodd}$ are not $e$-positive in Lemma~\ref{lem:as_notepos}, together giving Theorem~\ref{the:asnotpositive}. 

Finally, in Section~\ref{sec:towers} we introduce the family of triangular tower graphs, $\trt _{a,b,c}$, where $a,b,c\geq 2$, and prove in Lemma~\ref{lem:trt_ccf} that they are claw-free and do not contract to the claw, and for $n\geq3$ prove in Lemma~\ref{lem:trt_notepos} that $X_{\trtn}$ is not $e$-positive, together giving Theorem~\ref{the:trtnotpositive}, hence showing that the $e$-positivity of chromatic symmetric functions is not dependent on either being claw-free, or being not contractible to the claw. In all cases we see that classical techniques  suffice to yield our proofs, though a number of technical lemmas such as Lemma~\ref{lem:coeff_power_G_n,n,n} are required to yield the final theorems.

\section{Background}\label{sec:background}%%%
We begin by recalling some necessary combinatorial, algebraic and graph theoretic results that will be useful later. A \emph{partition} $\lambda = (\lambda_1, \lambda_2, \ldots , \lambda_{\ell(\lambda)})$ of $N$, denoted by $\lambda \vdash N$, is a list of positive integers whose \emph{parts} $\lambda_i$ satisfy $\lambda_1\geq \lambda _2\geq \cdots \geq\lambda_{\ell(\lambda)} >0$ and $\sum _{i=1}^{\ell(\lambda)} \lambda _i = N$.  If $\lambda$ has exactly $m_i$ parts equal to $i$ for $1\leq i \leq N$ we often denote $\lambda$ by $\lambda = (1^{m_1}, 2^{m_2}, \ldots , N^{m_N})$.

The algebra of symmetric functions is a subalgebra of $\bQ [[ x_1, x_2, \ldots ]]$ that can be defined as follows. The \emph{$i$-th elementary symmetric function} $e_i$ for $i\geq 1$ is given by
$$e_i = \sum _{j_1<j_2<\cdots < j_i} x_{j_1}x_{j_2}\cdots x_{j_i}$$and given a partition $\lambda = (\lambda _1, \lambda_2, \ldots , \lambda _{\ell(\lambda)})$  the \emph{elementary symmetric function} $e_\lambda$ is given by
$$e_\lambda = e_{\lambda _1}e_{\lambda _2}\cdots e_{\lambda _\ell}.$$The \emph{algebra of symmetric functions}, $\Lambda$, is then the graded algebra
$$\Lambda = \Lambda ^0 \oplus \Lambda ^1 \oplus \cdots$$where $\Lambda ^0 = \spam \{1\} = \bQ$ and for $N\geq 1$
$$\Lambda ^N = \spam \{e_\lambda \suchthat \lambda \vdash N\}.$$Moreover, the elementary symmetric functions form a basis for $\Lambda$ and if a symmetric function can be written as a non-negative linear combination of elementary symmetric functions, then we say it is \emph{$e$-positive}.

However, while the basis of elementary symmetric functions is central to the statement we wish to resolve, it is another basis, the basis of power sum symmetric functions, which will be central to our proofs. In terms of elementary symmetric functions the \emph{$i$-th power sum symmetric function} $p_i$ for $i\geq 1$ is given by
\begin{equation}
p_i= \sum_{\mu=(1^{m_1},2^{m_2},\ldots ,i^{m_i}) \vdash i}(-1)^{i-\ell(\mu)}\frac{i(\ell(\mu)-1)!}{\prod_{j=1}^{i}m_j!}e_{\mu}
\label{eq:newton}
\end{equation}and given a partition $\lambda = (\lambda _1, \lambda_2, \ldots , \lambda _{\ell(\lambda)})$  the \emph{power sum symmetric function} $p_\lambda$ is given by
$$p_\lambda = p_{\lambda _1}p_{\lambda _2}\cdots p_{\lambda _\ell}.$$This particular basis, of  power sum symmetric functions, will be useful later, as will the following. Given two partitions $\lambda, \mu \vdash N$ we write $\lambda \coarsep \mu$ if the parts of $\lambda$ are obtained by summing (not necessarily adjacent) parts of $\mu$. For example, $(5,4,2)\coarsep (3,3,2,2,1)$ since $5=3+2$, $4=3+1$ and $2=2$. Therefore by Equation~\eqref{eq:newton} we get the following key observation.

\begin{observation}\label{obs:newton}
When calculating the coefficient of $e_\mu$ in a symmetric function written in the basis of power sum symmetric functions, we need only focus on those $p_\lambda$ where $\lambda \coarsep \mu$.
\end{observation}

Since we will often want to compute the coefficient of a symmetric function $f\in \Lambda$ when written in the basis $\{b_\lambda \} _{\lambda \vdash N \geq 1}$, we will denote this by $[b_\lambda]f$. More details on these classical symmetric functions can be found in texts such as \cite{MacD, Sagan, ECII}, but for now we turn our attention to a more recent symmetric function, the chromatic symmetric function.

The chromatic symmetric function is reliant on a graph that is \emph{finite} and \emph{simple} and from now on we will assume that all our graphs satisfy these properties. This function is also reliant on all proper colourings of a graph. More precisely, given a graph, $G$, with vertex set $V$ a \emph{proper colouring} $\kappa$ of $G$ is a function
$$\kappa : V\rightarrow \{1,2,\ldots\}$$such that if $v_1, v_2 \in V$ are adjacent, then $\kappa(v_1)\neq \kappa(v_2)$. With this in mind we can now define the chromatic symmetric function, which we do in two ways before giving an example in Example~\ref{ex:claw}.

\begin{definition}\cite[Definition 2.1]{Stan95}\label{def:chromsym} For a graph $G$ with vertex set $V=\{v_1, v_2, \ldots, v_N\}$ and edge set $E$, the \emph{chromatic symmetric function} is defined to be
$$X_G = \sum _\kappa x_{\kappa(v_1)}x_{\kappa(v_2)}\cdots x_{\kappa(v_N)}$$
where the sum is over all proper colourings $\kappa$ of $G$. \end{definition}

For succinctness, we will say a graph \emph{$G$ is $e$-positive} or \emph{not}, to mean that $X_G$ is $e$-positive or not, respectively.

A more useful realisation of the chromatic symmetric function for us will be the following lemma, also due to Stanley, which requires some more notation. Given a graph $G$  with vertex set $V=\{v_1, v_2, \dots, v_N\}$, edge set $E$, and a subset $S\subseteq E$, let $\lambda(S)$ be the partition of $N$ whose parts are equal to the number of vertices in the connected components of the spanning subgraph of $G$ with vertex set $V$ and edge set $S$. If the number of vertices in a connected component is $\lambda _i$, then for succinctness we may refer to the connected component as a \emph{piece of size $\lambda_i$}. 



\begin{lemma}\label{lem:stanley}\cite[Theorem 2.5]{Stan95} For a graph $G$ with vertex set $V$ and  edge set $E$ we have that
$$X_G=\sum_{S\subseteq E} (-1)^{|S|} p_{\lambda(S)}.$$
\end{lemma}

\begin{example}\label{ex:claw} The \emph{claw} (also known as $K_{1,3}$ or, as in Stanley's quote, $K_{13}$) shown %in Figure~\ref{fig:claw} 
below has chromatic symmetric function
$$p_{(1^4)}-3p_{(2,1^2)}+3p_{(3,1)}-p_{(4)}=e_{(2,1^2)}-2e_{(2,2)}+5e_{(3,1)}+4e_{(4)}.$$
Thus, the claw is not $e$-positive.\end{example}

\pagebreak
\begin{figure}[h]\label{fig:claw}
\begin{center}
\begin{tikzpicture}[scale=1]
\coordinate (1) at (0,0);
\coordinate (2) at (1,1);
\coordinate (3) at (1.4,0);
\coordinate (4) at (1,-1);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (1)--(3);
\draw[->] (1)--(4);
\end{tikzpicture}
\end{center}
\caption{The claw.}
\end{figure}



%%%%

While the focus of our paper will be on the claw, a number of well known graphs will also play a role: The complete graph, $K_N, N\geq 1$; the \emph{$N$-path}, $P_N, N\geq 1$; and the \emph{$N$-cycle}, $C_N, N\geq 3$, and we set $C_i=K_i$ for $i=1,2$. Two particular claw related properties of a graph will also be much in demand, the property of being claw-free and of being \ccf.

For the former recall that an \emph{induced} subgraph of a graph $G$ is a subgraph consisting of a subset of its vertices together with all edges whose endpoints both lie in the subset, and an \emph{edge induced} subgraph of a graph $G$ is a subgraph consisting of a subset of its edges together with all vertices at the endpoints of every edge in the subset.

We say a graph is \emph{claw-free} if it does not have the claw as an induced subgraph. Claw-free graphs have the following characterization due to Beineke \cite[Theorem]{Beineke} who combined the results of Krausz \cite[Theorem 1]{Krausz} and van Rooij and Wilf \cite[Theorem 4]{vRW}.

\begin{lemma}\label{lem:beineke}\cite[Theorem]{Beineke}
A graph $G$ is claw-free if and only if there exists a partition of the edges of $G$ into disjoint sets, such that every set edge induces a complete subgraph of $G$ and no vertex  of $G$ belongs to more than 2 of these complete subgraphs.
\end{lemma}

For the latter, let $G$ be a graph with vertex set $V$ and edge set $E$. Recall a subset of $V$ is \emph{independent} if no two vertices in the subset are adjacent, plus when we delete a vertex $v$ from $G$ we delete  $v$ and all edges incident to $v$. Furthermore, if $S\subseteq E$, then we denote by $G/S$ the graph $G$ with the edges in $S$ contracted and the vertices at either end identified. We say that $G$ contracts to the claw if there exists $S\subseteq E$ such that $G/S$ yields the claw once multiple edges are replaced by single edges, and $G$ is \emph{\ccf}\ if $G$ does not contract to the claw. 

As with being claw-free, an elegant characterization exists for a graph to be \ccf. It is dependent on deleting  independent sets of vertices, and is a special case of a theorem by Brouwer and Veldman \cite[Theorem 3]{BV}.

\begin{lemma}\label{lem:BV}\cite[Theorem 3]{BV} A graph $G$ is \ccf\ if and only if the deletion of any set of 3 independent vertices from $G$ results in a disconnected graph.
\end{lemma}

We now turn our attention to the graphs with the fewest number of vertices that are \ccf\ and not $e$-positive. Since a disconnected graph cannot contract to the claw, we restrict ourselves to \emph{connected} graphs in order to yield a meaningful resolution to Stanley's statement. 

Otherwise,  by \cite[Propositon 2.3]{Stan95}, which says for disjoint graphs $G,H$ we have that
$$X_{G\cup H}=X_GX_H,$$ calculating $X_{K_1}=e_1$, and Example~\ref{ex:claw}, we can conclude that the disjoint union of the claw and $K_1$ is a trivial resolution to Stanley's statement.

Using an exhaustive computational search, the connected graphs with the fewest number of vertices, $N$, that are \ccf\ and not $e$-positive occur at $N=6$ and are given in Figure~\ref{fig:4counter}.

\begin{figure}[h]\label{fig:4counter}
\begin{center}
%%%Circle cross graph
\begin{tikzpicture}[scale=1]
\begin{scope}[shift={(0,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (1)--(2)--(3)--(4)--(5)--(6)--(1);
\end{scope}
%%%Circle cross graph with extra edge
\begin{scope}[shift={(4,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (3)--(5);
\draw[->] (1)--(2)--(3)--(4)--(5)--(6)--(1);
\end{scope}
%%%K_{3,3}
\begin{scope}[shift={(8,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (1)--(4);
\draw[->] (1)--(2)--(3)--(4)--(5)--(6)--(1);
\end{scope}
%%%K_{3,3} with extra edge
\begin{scope}[shift={(12,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (3)--(5);
\draw[->] (1)--(4);
\draw[->] (1)--(2)--(3)--(4)--(5)--(6)--(1);
\end{scope}
\end{tikzpicture}
\end{center}
\caption{From left to right the graphs $\sa _{3,3}, \as _{3,3}, K_{3,3}, AK_{3,3}$.}
\end{figure}

In particular, their chromatic symmetric functions are
$$\begin{array}{lclclclclcl}
X_{\sa _{3,3}}&=&2e_{(2,2,2)}&-&6e_{(3,3)}&+&26e_{(4,2)}&+&28e_{(5,1)}&+&102e_{(6)}\\
X_{\as _{3,3}}&=&2e_{(3,2,1)}&-&6e_{(3,3)}&+&24e_{(4,2)}&+&40e_{(5,1)}&+&120e_{(6)}\\
X_{K _{3,3}}&=&2e_{(2,2,2)}&-&12e_{(3,3)}&+&30e_{(4,2)}&+&24e_{(5,1)}&+&186e_{(6)}\\
X_{AK _{3,3}}&=&2e_{(3,2,1)}&-&6e_{(3,3)}&+&20e_{(4,2)}&+&32e_{(5,1)}&+&228e_{(6)}.
\end{array}$$

As we will see in the next section, the leftmost two graphs each naturally give rise to infinite families of graphs that are \ccf, are not $e$-positive and, moreover, we can explicitly identify and calculate a negative coefficient. 

\section{Saltire and augmented saltire graphs}\label{sec:saltires}
In this section we begin by introducing our first infinite family of graphs to resolve Stanley's statement. In particular, this family includes the graph with the fewest number of vertices and edges, as verified by computer, which is \ccf\ and yet whose chromatic symmetric function is not $e$-positive.

The \emph{saltire graph} $\sa _{a,b}$, where $a,b \geq 2$, is the graph on $a+b$  vertices $\{v_1, v_2, \ldots , v_{a+b}\}$ with edges $v_iv_{i+1}$ for $1\leq i \leq a+b-1$, $v_{a+b}v_1$, $v_1v_{a+1}$ and $v_2v_{a+2}$. For example, $\sa _{2,2}= K_4$, and $\sa _{3,3}$ and a graphical representation of a generic $\sa _{a,b}$ are given in Figure~\ref{fig:saltires}.

\pagebreak

\begin{figure}[h]\label{fig:saltires}
\begin{center}
\begin{tikzpicture}[scale=1]
%Circle cross graph G_33
\begin{scope}[shift={(0,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (-.5,0) node {$v_3$};
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (3.5,0) node {$v_6$};
\draw (2.4,-1.55) node {$v_5$};
\draw (.5,-1.55) node {$v_4$};
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (1)--(2)--(3)--(4)--(5)--(6)--(1);
\end{scope}
%Circle cross graph G_a,b
\begin{scope}[shift={(6,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw[dashed] (2) arc (90:270:1.25);
\draw[dashed] (3) arc (90:-90:1.25);
\draw (-.4,0) node {$a$-path};
\draw (3.5,0) node {$b$-path};
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{a+2}$};
\draw (.5,-1.7) node {$v_{a+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (2)--(3);
\draw[->] (5)--(6);
\end{scope}
\end{tikzpicture}
\end{center}
\caption{From left to right we have $\sa _{3,3}$ and a generic $\sa_{a,b}$.}
\end{figure}


From the graphical representation we see that the edges of $\sa _{a,b}$ can be naturally partitioned into three parts as follows. Given $\sa _{a,b}$ we refer to the subgraph induced by the edges $$\{ v_iv_{i+1} \suchthat 2\leq i \leq a\}$$as the \emph{$a$-path}, the subgraph induced by the edges $$\{ v_iv_{i+1} \suchthat a+2\leq i \leq a+b-1\}\cup\{v_{a+b}v_1\}$$as the \emph{$b$-path}, and the subgraph induced by the edges $$\{ v_1v_2, v_1v_{a+1}, v_2v_{a+2}, v_{a+1}v_{a+2}\}$$as the \emph{middle}. Furthermore, when considering $\san$ we refer to the $a$-path, where $a=n$, as the \emph{left $n$-path}, and the $b$-path, where $b=n$, as the \emph{right $n$-path}, to distinguish them. With these definitions in hand, we come to our first result on saltire graphs.

\begin{lemma}\label{lem:sa_ccf} For all $a,b \geq 2$ the graph $\sa _{a,b}$ is \ccf. In particular, for $n\geq 3$ the graph $\san$ is \ccf.
\end{lemma}

\begin{proof} By Lemma~\ref{lem:BV} it suffices to show that the deletion of any three independent vertices from $\sa _{a,b}$ results in a disconnected graph. The pigeonhole principle guarantees that at least two of these independent vertices will belong to either the $a$-path or the $b$-path, and we can see from Figure~\ref{fig:saltires} that the removal of any two non-adjacent vertices from the $a$-path or the $b$-path results in a disconnected graph.
\end{proof}

Now that we have proved that $\sa _{a,b}$ is \ccf, we will restrict our attention to $\san$ where $n\geq 3$, and prove that its chromatic symmetric function is  not $e$-positive by calculating the coefficient $[e_{(n^2)}]X_{\san}$. Note that since $(2n)$ and $(n^2)$ are the only partitions $\lambda \vdash 2n$ satisfying $\lambda \coarsep (n^2)$ by Observation~\ref{obs:newton} and Lemma~\ref{lem:stanley}, in order to calculate $[e_{(n^2)}]X_{\san}$ we need to calculate $[p_{(2n)}]X_{\san}$ and $[p_{(n^2)}]X_{\san}$.



%%% SAM START

\begin{table}
\begin{center}
\begin{tabular}{| c |c|}
\hline
$i$& $\sa_{n,n}$  with $i$ middle edges removed\\
\hline
1&
%%%%Figure of G_2n with one edge missing%%
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (3)--(6);
\draw[->] (2)--(3);
\draw[->] (5)--(6);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (2)--(3);
\draw[->] (5)--(6);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (5)--(6);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (2)--(3);
\end{tikzpicture}\\
\hline
2& 
%%%%Figure of G_2n with two edges missing%%
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(3);
\draw[->] (5)--(6);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (3)--(6);
\draw[->] (5)--(6);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (3)--(6);
\draw[->] (2)--(3);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (5)--(6);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (2)--(3);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\end{tikzpicture}\\
\hline
3&
%%%%Figure of G_2n with three edges missing%%
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (5)--(6);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(3);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (3)--(6);
\end{tikzpicture}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (2) arc (90:270:1.25);
\draw (3) arc (90:-90:1.25);
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{n+2}$};
\draw (.5,-1.7) node {$v_{n+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\end{tikzpicture}\\
\hline
\end{tabular}
\end{center}
\caption{All possible $\sa _{n,n}$ with $1$ through $3$ middle edges removed.}
\label{table:G_2noptions}
\end{table}
%%%%%%%%%%%
%%%%%%%%end table%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{lemma}For  $n\geq 3$ we have that
\begin{enumerate}
\item $[p_{(2n)}]X_{\san}=-3n^2+4n-2$ and
\item $[p_{(n^2)}]X_{\san}=2n-1$.
\end{enumerate}
\label{lem:powercoeffgraph}
\end{lemma}

\begin{proof}
To prove this we will use Lemma~\ref{lem:stanley} that considers all subsets $S$ of the edge set $E$. 
We are only interested in the subsets $S$ that yield $\lambda(S) = (2n)$ or $(n^2)$ both of which have parts  that are at least $n$. This means we will ignore any $S$ where $\lambda(S)$ has a part smaller than $n$ as these subsets will  not affect the coefficient of $p_{(2n)}$ or $p_{(n^2)}$ in $X_{\san}$. Note that if  $S$ has two or more edges removed from the left   $n$-path (or the right $n$-path), then $\lambda(S)$ certainly has a part  smaller than $n$. Thus, we will only consider subsets $S$ that have \emph{at most one edge} removed from the left $n$-path and \emph{at most one edge} removed from the right $n$-path. 
In Table~\ref{table:G_2noptions} we illustrate all possible graphs  with $1$ through $3$  middle edges removed from $\san$ since these will be central to our case analysis, consisting of 5 cases corresponding to the exclusion of 0 to 4 edges from $E$. 

First, consider $|S|=|E|$, so $S$ contains all the edges in $E$. This gives us the term $$(-1)^{2n+2}p_{(2n)}= p_{(2n)}.$$ 

Second, consider $|S|=|E|-1$, so $S$ has one fewer edge than $E$. Note that if we remove any one of the $2n+2$ edges from $\san$, then our graph is still connected. This gives us the term $$(-1)^{2n+1}(2n+2)p_{(2n)}= -(2n+2)p_{(2n)}.$$ 

Third, consider $|S|=|E|-2$, so $S$ has two fewer edges than $E$. If we exclude two edges from the middle, then we can see from Table~\ref{table:G_2noptions}  that all six possibilities result in connected graphs so we get the term $(-1)^{2n}6p_{(2n)}$. 

Instead we can exclude one edge  from the left $n$-path or right $n$-path and the other edge from the middle.  In  all four ways to  remove one edge  from  the middle, as illustrated in Table~\ref{table:G_2noptions}, we can also remove any one of the  $2(n-1)$ edges on the left $n$-path or right $n$-path and still have a connected graph. This gives us the term $(-1)^{2n}8(n-1)p_{(2n)}$. 

Finally, we could exclude no  edges from the middle, one of the $n-1$ edges from the left $n$-path, and one of the $n-1$ edges from the right $n$-path. Any of the $(n-1)^2$ choices  results in a  connected graph. This gives us the term $(-1)^{2n}(n-1)^2p_{(2n)}$.

Altogether from this case we have the term $$(n^2+6n-1)p_{(2n)}.$$

Fourth, consider $|S|=|E|-3$, where we exclude three edges from $E$. We can see from Table~\ref{table:G_2noptions} that excluding any three edges from  the middle leaves the graph  connected. This gives the term $(-1)^{2n-1}4p_{(2n)}$.  

If instead we remove two edges from the middle and one of the $n-1$ edges from the left $n$-path we can see from Table~\ref{table:G_2noptions} that only four out of six possibilities do not yield $\lambda(S)$ to have  a part smaller than $n$.  In these four possibilities  the graph is connected, which gives us the term $(-1)^{2n-1}4(n-1)p_{(2n)}$. We similarly get the term $(-1)^{2n-1}4(n-1)p_{(2n)}$ if we remove two  edges from the middle, one from the right $n$-path, and have all parts being at least $n$. 

Lastly, if we remove one edge from the middle, any one of the $n-1$ edges from the right $n$-path, and any one of the $n-1$ edges from the left $n$-path, then we can see from Table~\ref{table:G_2noptions} that the graph is still connected. This gives us the term $(-1)^{2n-1}4(n-1)^2p_{(2n)}$. 

Altogether from this case we get the term $$-4n^2p_{(2n)}.$$

Fifth and finally, consider $|S|=|E|-4$. If we exclude all four of the edges from the middle, then this disconnects our graph into two pieces of size $n$. The associated term is $(-1)^{2n-2}p_{(n^2)}$. 

Say we exclude three edges from the middle and one from the left $n$-path or right $n$-path. In any of these situations $\lambda(S)$ has a part smaller than $n$. 

Instead say that we remove two edges from the middle, one from the left $n$-path, and one from the right $n$-path. From  Table~\ref{table:G_2noptions} we can see that in only the  leftmost and rightmost pictures that  $\lambda(S)$ is not forced to have a part smaller than $n$. In the   leftmost and rightmost  pictures we will disconnect the graph into two pieces. For  any of the $n-1$ edges on the left $n$-path there is exactly one choice of an edge on the right $n$-path so that we break the graph into two pieces of size $n$. This gives the  term $(-1)^{2n-2}2(n-1)p_{(n^2)}$. 

Altogether from this case we get the term $$(2n-1)p_{(n^2)}.$$

Once we exclude more than four edges from $E$ we are guaranteed that $\lambda(S)$ will have  a part smaller  than $n$. Combining everything the coefficient of $p_{(2n)}$ is therefore
$$[p_{(2n)}]X_{\san}=1-(2n+2)+(n^2+6n-1)-4n^2=-3n^2+4n-2$$
and 
$$[p_{(n^2)}]X_{\san}=2n-1$$
is the  coefficient for $p_{(n^2)}$. 
\end{proof}

\begin{lemma} For $n\geq 1$ we have that 
\begin{enumerate}
\item $[e_{(n^2)}]p_{(2n)}=n$ and
\item $[e_{(n^2)}]p_{(n^2)}=n^2$. 
\end{enumerate}
\label{lem:elemcoeffpower}
\end{lemma}

\begin{proof}
Using Equation~\eqref{eq:newton} we have that $[e_{(n^2)}]p_{(2n)}=(-1)^{2n-2}\frac{2n(2-1)!}{2!}=n$. 

To prove the other coefficient note by Equation~\eqref{eq:newton} that $[e_{n}]p_{n}=(-1)^{n-1}\frac{n(1-1)!}{1!}=(-1)^{n-1}n$. In $p_{(n^2)}=p_np_n$ the coefficient of $e_{(n^2)}$ is purely determined by the multiplication of the coefficients of $e_{n}$ in  $p_n$, which gives $[e_{(n^2)}]p_{(n^2)}=[e_{n}]p_{n}[e_{n}]p_{n}=(-1)^{n-1}n(-1)^{n-1}n=n^2$. 
\end{proof}

We now apply these lemmas to determine the $e$-positivity of $X_{\san}$ for $n\geq 3$ in one final lemma.

\begin{lemma}\label{lem:sa_notepos}
The chromatic symmetric function of $\san$ for $n\geq 3$ is not $e$-positive. In particular, we have that
$$[e_{(n^2)}]X_{\san}=-n(n-1)(n-2).$$
\end{lemma}

\begin{proof}
By Observation~\ref{obs:newton} we can see that  $e_{(n^2)}$ has non-zero coefficient in $p_{\lambda}$ only for  $\lambda\vdash 2n$ with $\lambda\coarsep (n^2)$. There are only two partitions $\lambda\vdash 2n$ where $\lambda\coarsep (n^2)$, namely $(2n)$ and $(n^2)$. 

Since 
$$X_{\san}=\sum_{\lambda\vdash 2n}[p_{\lambda}]X_{\san} p_{\lambda}$$
the coefficient of $e_{(n^2)}$ in $X_{\san}$ only arises from the  $p_{(2n)}$ and $p_{(n^2)}$ terms. In particular, $$[e_{(n^2)}]X_{\san}=[e_{(n^2)}]p_{(2n)}\cdot [p_{(2n)}]X_{\san}+[e_{(n^2)}]p_{(n^2)}\cdot[p_{(n^2)}]X_{\san}.$$ Using  Lemma~\ref{lem:powercoeffgraph} and Lemma~\ref{lem:elemcoeffpower} we therefore have
\begin{align*}
[e_{(n^2)}]X_{\san}&=[e_{(n^2)}]p_{(2n)}\cdot [p_{(2n)}]X_{\san}+[e_{(n^2)}]p_{(n^2)}\cdot[p_{(n^2)}]X_{\san}\\
&=n\cdot (-3n^2+4n-2)+n^2\cdot (2n-1)\\
&=-n(n-1)(n-2).
\end{align*}
\end{proof}




%%%SAM END

We can now identify our first family of graphs that are \ccf, and whose chromatic symmetric functions are not $e$-positive.

\begin{theorem}\label{the:sanotpositive} The graphs $\san$ for all $n\geq 3$ are \ccf\ and not $e$-positive.
\end{theorem}

\begin{proof} This follows immediately from Lemmas~\ref{lem:sa_ccf} and \ref{lem:sa_notepos}.
\end{proof}

Since Theorem~\ref{the:sanotpositive} yields an infinite family of graphs with an even number of vertices that are \ccf\ and not $e$-positive, a natural question to ask is whether an infinite family of graphs exists with $N$ vertices, for all $N\geq 6$, which are \ccf\ and not $e$-positive. Such a family exists and is the family of \emph{augmented} saltire graphs, which we introduce now.

The \emph{augmented saltire graph} $\as _{a,b}$, where $a\geq 2, b\geq 3$, is the saltire graph $\sa _{a,b}$ with the additional edge $v_1v_{a+2}$. More precisely, $\as _{a,b}$, where $a\geq 2, b\geq 3$, is the graph on $a+b$  vertices $\{v_1, v_2, \ldots , v_{a+b}\}$ with edges $v_iv_{i+1}$ for $1\leq i \leq a+b-1$, $v_{a+b}v_1$, $v_1v_{a+1}$, $v_2v_{a+2}$ and $v_1v_{a+2}$. For example, $\as _{3,3}$,  $\as _{3,4}$ and a graphical representation of a generic $\as _{a,b}$ are given in Figure~\ref{fig:augsaltires}. 

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=1]
%Circle cross graph with extra edge G*_33
\begin{scope}[shift={(0,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw (-.5,0) node {$v_3$};
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (3.5,0) node {$v_6$};
\draw (2.4,-1.55) node {$v_5$};
\draw (.5,-1.55) node {$v_4$};
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (3)--(5);
\draw[->] (1)--(2)--(3)--(4)--(5)--(6)--(1);
\end{scope}
%Circle cross graph with extra edge G*_34
\begin{scope}[shift={(5.2,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,-.5);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\coordinate (7) at  (3,.5);
\draw (-.5,0) node {$v_3$};
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (3.5,.5) node {$v_7$};
\draw (3.5,-.5) node {$v_6$};
\draw (2.4,-1.55) node {$v_5$};
\draw (.5,-1.55) node {$v_4$};
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\filldraw [black] (7) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (3)--(5);
\draw[->] (1)--(2)--(3)--(7)--(4)--(5)--(6)--(1);
\end{scope}
%Circle cross graph with extra edge G*_a,b
\begin{scope}[shift={(10.5,0)}]
\coordinate (1) at (0,0);
\coordinate (2) at (.8,1.25);
\coordinate (3) at (2.2,1.25);
\coordinate (4) at (3,0);
\coordinate (5) at (2.2,-1.25);
\coordinate (6) at  (.8,-1.25);
\draw[dashed] (2) arc (90:270:1.25);
\draw[dashed] (3) arc (90:-90:1.25);
\draw (-.4,0) node {$a$-path};
\draw (3.5,0) node {$b$-path};
\draw (.5,1.55) node {$v_2$};
\draw (2.4,1.55) node {$v_1$};
\draw (2.4,-1.7) node {$v_{a+2}$};
\draw (.5,-1.7) node {$v_{a+1}$};
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(5);
\draw[->] (3)--(6);
\draw[->] (3)--(5);
\draw[->] (2)--(3);
\draw[->] (5)--(6);
\end{scope}
\end{tikzpicture}
\end{center}
\caption{From left to right we have $\as _{3,3}$, $\as _{3,4}$ and a generic $\as_{a,b}$.}
\label{fig:augsaltires}
\end{figure}

Using proofs very similar to those for saltire graphs, but with some additional cases generated by the edge $v_1v_{a+2}$, we can obtain the following two lemmas.

\begin{lemma}\label{lem:as_ccf} For all $a\geq 2, b\geq 3$ the graph $\as _{a,b}$ is \ccf. In particular, for $n\geq 3$ the graphs $\aseven$ and $\asodd$ are \ccf.
\end{lemma}

\begin{lemma}\label{lem:coeffG^*n,n+1} For $n\geq 3$ we have that
\begin{enumerate}
\item $[p_{(2n)}]X_{\aseven}= -4n^2+6n-2$,
\item $[p_{(n^2)}]X_{\aseven}= 3n-3$,
\item $[p_{(2n+1)}]X_{\asodd}= 4n^2-2n$ and
\item $[p_{(n+1,n)}]X_{\asodd}=-7n+4$.
\end{enumerate}
\end{lemma}

We also obtain the following lemma whose proof is analogous to that of Lemma~\ref{lem:elemcoeffpower}.

\begin{lemma}\label{lem:elemcoeffpower2} For $n\geq 1$ we have that
\begin{enumerate}
\item $[e_{(n+1, n)}]p_{(2n+1)}=-(2n+1)$ and
\item $[e_{(n+1, n)}]p_{(n+1,n)}= -n(n+1)$.
\end{enumerate}
\end{lemma}

From  here we are able to determine the $e$-positivity of $X_{\aseven}$ and $X_{\asodd}$ for $n\geq 3$.

\begin{lemma}\label{lem:as_notepos} 
The chromatic symmetric functions of ${\aseven}$ and ${\asodd}$ for $n\geq 3$ are not $e$-positive. In particular, we have that
$$[e_{(n^2)}]X_{\aseven}=[e_{(n+1,n)}]X_{\asodd}=-n(n-1)(n-2).$$
\end{lemma}

\begin{proof}
By Observation~\ref{obs:newton} we can see that  $e_{(n^2)}$ has non-zero coefficient in $p_{\lambda}$ only for  $\lambda\vdash 2n$ with $\lambda\coarsep (n^2)$. There are only two partitions $\lambda\vdash 2n$ where $\lambda\coarsep (n^2)$, namely $(2n)$ and $(n^2)$. 

Since 
$$X_{\aseven}=\sum_{\lambda\vdash 2n}[p_{\lambda}]X_{\aseven} p_{\lambda}$$
the coefficient of $e_{(n^2)}$ in $X_{\aseven}$ only arises from the  $p_{(2n)}$ and $p_{(n^2)}$ terms. In particular, $$[e_{(n^2)}]X_{\aseven}=[e_{(n^2)}]p_{(2n)}\cdot [p_{(2n)}]X_{\aseven}+[e_{(n^2)}]p_{(n^2)}\cdot[p_{(n^2)}]X_{\aseven}.$$ Using  Lemma~\ref{lem:coeffG^*n,n+1} and Lemma~\ref{lem:elemcoeffpower}  we therefore have
\begin{align*}
[e_{(n^2)}]X_{\aseven}&=[e_{(n^2)}]p_{(2n)}\cdot [p_{(2n)}]X_{\aseven}+[e_{(n^2)}]p_{(n^2)}\cdot[p_{(n^2)}]X_{\aseven}\\
&=n\cdot (-4n^2+6n-2)+n^2\cdot (3n-3)\\
&=-n(n-1)(n-2).
\end{align*}

Again by Observation~\ref{obs:newton} we can see that  $e_{(n+1,n)}$ has non-zero coefficient in $p_{\lambda}$ only for  $\lambda\vdash 2n+1$ with $\lambda \coarsep (n+1,n)$. There are only two partitions $\lambda\vdash 2n+1$ where $\lambda\coarsep (n+1,n)$, namely $(2n+1)$ and $(n+1,n)$. 

Since 
$$X_{\asodd}=\sum_{\lambda\vdash 2n+1}[p_{\lambda}]X_{\asodd} p_{\lambda}$$
the coefficient of $e_{(n+1,n)}$ in $X_{\asodd}$ only arises from the  $p_{(2n+1)}$ and $p_{(n+1,n)}$ terms. In particular, $$[e_{(n+1,n)}]X_{\asodd}=[e_{(n+1,n)}]p_{(2n+1)}\cdot [p_{(2n+1)}]X_{\asodd}+[e_{(n+1,n)}]p_{(n+1,n)}\cdot[p_{(n+1,n)}]X_{\asodd}.$$Using  Lemma~\ref{lem:coeffG^*n,n+1} and Lemma~\ref{lem:elemcoeffpower2}  we therefore have
\begin{align*}
[e_{(n+1,n)}]X_{\asodd}&=[e_{(n+1,n)}]p_{(2n+1)}\cdot [p_{(2n+1)}]X_{\asodd}+[e_{(n+1,n)}]p_{(n+1,n)}\cdot[p_{(n+1,n)}]X_{\asodd}\\
&=-(2n+1)\cdot (4n^2-2n)-n(n+1)\cdot (-7n+4)\\
&=-n(n-1)(n-2).
\end{align*}
\end{proof}


We can now identify our second family of graphs that are \ccf\ and whose chromatic symmetric functions are not $e$-positive, and, moreover, one such graph exists with $N$ vertices for all $N\geq 6$.

\begin{theorem}\label{the:asnotpositive} The graphs $\aseven$ and $\asodd$ for all $n\geq 3$ are \ccf\ and not $e$-positive.
\end{theorem}

\begin{proof} This follows immediately from Lemmas~\ref{lem:as_ccf} and \ref{lem:as_notepos}.
\end{proof}




\section{Triangular tower graphs}\label{sec:towers}

Considering Stanley's $(\mbox{\textbf{3}}+\mbox{\textbf{1}})$-free conjecture \cite[Conjecture 5.1]{Stan95}, a final natural question to answer is a refinement of Stanley's \ccf\ statement. More precisely, does there exist a graph that is \ccf\ \emph{and} claw-free whose chromatic symmetric function is not $e$-positive? By exhaustive computational search the smallest such example is

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.7]
\begin{scope}
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,3);
\coordinate (5) at (1,4);
\coordinate (6) at (-1,4);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\filldraw [black] (-1,2) circle (4pt);
\filldraw [black] (0,2) circle (4pt);
\filldraw [black] (1,2) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (1)--(3);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (6)--(5);
\draw[->] (4)--(6);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{scope}
\end{tikzpicture}
\end{center}
\end{figure}

\noindent with chromatic symmetric function
\begin{align*}&12e_{(3,3,2,1)}-12e_{(3,3,3)}+102e_{(4,3,2)}+90e_{(4,4,1)}
+18e_{(5,2,2)}+96e_{(5,3,1)}\\&+294e_{(5,4)}+30e_{(6,2,1)}
+180e_{(6,3)}+342e_{(7,2)}+294e_{(8,1)}+666e_{(9)}\end{align*}and, moreover, it yields an infinite family of graphs that are \ccf, claw-free and not $e$-positive, the triangular tower graphs.

The \emph{triangular tower graph} $\trt _{a,b,c}$, where $a,b,c\geq 2$, is the graph on $a+b+c$ vertices
$$\{v_1,\ldots,v_{a}\}\cup\{v_{a+1},\ldots,v_{a+b}\}\cup\{v_{a+b+1},\ldots,v_{a+b+c}\}$$with edges
$v_iv_{i+1}$ for $$i\in \{1,\ldots ,a-1\}\cup\{a+1,\ldots, a+b-1\}\cup\{a+b+1,\ldots,a+b+c-1\}$$plus $\{v_1v_{a+1}, v_{a+1}v_{a+b+1}, v_{a+b+1}v_1\}$ and $\{v_av_{a+b}, v_{a+b}v_{a+b+c}, v_{a+b+c}v_a\}$. Informally we can visualize $\trt _{a,b,c}$ as consisting of three disjoint paths with, respectively, $a,b,c$ vertices where we take one leaf from each path and connect them in a triangle to form an induced $K_3$, and do the same with the remaining three leaves. For example, $\trt _{3,2,4}, \trt _{3,3,3}$ and a graphical representation of a generic $\trt _{a,b,c}$ are given in Figure~\ref{fig:tt}.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=.7]
\begin{scope}[shift={(0,0)}]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,3);
\coordinate (5) at (1,4);
\coordinate (6) at (-1,4);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\filldraw [black] (-1,2) circle (4pt);
\filldraw [black] (1,1.3) circle (4pt);
\filldraw [black] (1,2.6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (1)--(3);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (6)--(5);
\draw[->] (4)--(6);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{scope}
\begin{scope}[shift={(4.5,0)}]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,3);
\coordinate (5) at (1,4);
\coordinate (6) at (-1,4);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\filldraw [black] (-1,2) circle (4pt);
\filldraw [black] (0,2) circle (4pt);
\filldraw [black] (1,2) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (1)--(3);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (6)--(5);
\draw[->] (4)--(6);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{scope}
\begin{scope}[shift={(10,0)}]
\coordinate (1) at (-2,0);
\coordinate (2) at (0,1);
\coordinate (3) at (2,0);
\coordinate (4) at (0,3);
\coordinate (5) at (2,4);
\coordinate (6) at (-2,4);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (1)--(3);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (6)--(5);
\draw[->] (4)--(6);
\draw[dashed] (1)--(6);
\draw[dashed] (2)--(4);
\draw[dashed] (5)--(3);
\draw (-1.9,2) node {$a$-path};
\draw (.1,2) node {$b$-path};
\draw (2.1,2) node {$c$-path};
\end{scope}
\end{tikzpicture}
\end{center}
\caption{From left to right we have $\trt_{3,2,4}$,  $\trt_{3,3,3}$ and a generic $\trt_{a,b,c}$.}
\label{fig:tt}
\end{figure}

Given $\trt _{a,b,c}$ we refer to the subgraphs induced by the edges
$$\{ v_iv_{i+1}\suchthat 1\leq i \leq a-1\}$$
as the \emph{$a$-path},
$$\{ v_iv_{i+1}\suchthat a+1\leq i \leq a+b-1\}$$
as the \emph{$b$-path} and
$$\{ v_iv_{i+1}\suchthat a+b+1\leq i \leq a+b+c-1\}$$
as the \emph{$c$-path}. Plus we refer to $\{v_1v_{a+1}, v_{a+1}v_{a+b+1}, v_{a+b+1}v_1\}$ as the \emph{top triangle}, and to $\{v_av_{a+b}, v_{a+b}v_{a+b+c}, v_{a+b+c}v_a\}$ as the \emph{bottom triangle}. 

As with the previous section we will focus on a subset of this family, namely $\trtn$. In this case we refer to the $a$-path, where $a=n$, as the \emph{left $n$-path}, the $b$-path, where $b=n$, as the \emph{middle $n$-path},  and the $c$-path, where $c=n$, as the \emph{right $n$-path}. We are now ready to ascertain the containment of the claw for this new family of graphs.

\begin{lemma}\label{lem:trt_ccf}  For all $a,b,c \geq 2$ the graph $\trt _{a,b,c}$ is \ccf\ and claw-free. In particular, for $n\geq 3$ the graph $\trtn$ is \ccf\ and claw-free.
\end{lemma} 



\begin{proof} 
We first show that $\trt _{a,b,c}$ is claw-free by demonstrating a partition of the edges into disjoint sets such that every set edge induces a complete subgraph and no vertex belongs to more than two of the subgraphs. The result will then follow by Lemma~\ref{lem:beineke}. Note that such a partition is given by the edges in the top triangle, and the bottom triangle, edge inducing a $K_3$ subgraph each, and each remaining edge likewise edge inducing a $K_2$ subgraph.

Now we show that $\trt _{a,b,c}$ is \ccf\ by showing that the deletion of any three independent vertices from $\trt _{a,b,c}$ results in a disconnected graph. The result will then follow by Lemma~\ref{lem:BV}. Note that the removal of at least two non-adjacent vertices from either the $a$-path, $b$-path, or $c$-path results in a disconnected graph. Similarly the removal of one vertex from each of the $a$-path, the $b$-path, and the $c$-path of $\trt _{a,b,c}$ results in a disconnected graph unless all three vertices belong to the top triangle, or to the bottom triangle, but neither of these sets of three vertices is itself independent.
\end{proof}

Having proved that $\trt _{a,b,c}$ is both \ccf\ and claw-free we restrict our attention to $\trtn$ where $n\geq3$ and prove that its chromatic symmetric function is not $e$-positive by calculating the coefficient $[e_{(n^3)}] X_{\trtn}$. Note that $(3n),(2n,n)$ and $(n^3)$ are the only partitions that satisfy $\lambda \vdash 3n$ and $\lambda \coarsep (n^3)$ and hence by Obsevation~\ref{obs:newton} and Lemma~\ref{lem:stanley} in order to calculate $[e_{(n^3)}] X_{\trtn}$, we need to calculate $[p_{(3n)}]X_{\trtn}$, $[p_{(2n,n)}]X_{\trtn}$ and $[p_{(n^3)}]X_{\trtn}$, which we do in the following lemma using a case analysis that is similar to, but more substantial and delicate than,  Lemma~\ref{lem:powercoeffgraph}.

%%%SAM START 2


\begin{table}
\begin{center}
\begin{tabular}{| c |c|}
\hline
$i$& $\trtn$  with $i$ edges removed from the triangles\\
\hline
1&
%%%%Figure of G_n,n,n with one edge missing%%
6 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (1)--(3);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (4)--(6);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture}\\
\hline
2& 
%%%% with two edges missing%%
6 of  \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (1)--(3);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture}, 
\hspace{.1in}3 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (4)--(6);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture},
\hspace{.1in}6 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(3);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (4)--(6);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture}\\
\hline
3&
%%%%with three edges missing%%
12 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (4)--(5);
\draw[->] (4)--(6);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture}, 
\hspace{.1in}6 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(3);
\draw[->] (4)--(5);
\draw[->] (4)--(6);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture},
\hspace{.1in}2 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (1)--(3);
\draw[->] (2)--(3);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture}\\
\hline
4&
%%%%with four edges missing%%
6 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (2)--(3);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture}, 
\hspace{.1in}6 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(2);
\draw[->] (4)--(5);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture},
\hspace{.1in}3 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (2)--(3);
\draw[->] (4)--(5);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture}\\
\hline
5&
%%%%with five edges missing%%
6 of \hspace{.03in}
\begin{tikzpicture}[scale=.5]
\coordinate (1) at (-1,0);
\coordinate (2) at (0,1);
\coordinate (3) at (1,0);
\coordinate (4) at (0,2);
\coordinate (5) at (1,3);
\coordinate (6) at (-1,3);
\filldraw [black] (1) circle (4pt);
\filldraw [black] (2) circle (4pt);
\filldraw [black] (3) circle (4pt);
\filldraw [black] (4) circle (4pt);
\filldraw [black] (5) circle (4pt);
\filldraw [black] (6) circle (4pt);
\draw[->] (1)--(3);
\draw[->] (1)--(6);
\draw[->] (2)--(4);
\draw[->] (5)--(3);
\end{tikzpicture}\\
\hline
\end{tabular}
\end{center}
\caption{All possible $\trtn$ with $1$ through $5$ edges removed from the top and bottom triangle.}
\label{table:G_n,n,noptions}
\end{table}
%%%%%%%%%%%
%%%%%%%%end table for triangular towers%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{lemma} For $n\geq 3$  we have that
\begin{enumerate}
\item $[p_{(3n)}]X_{\trtn}=(-1)^{3n+3}(12n^2-12n+2)$,
\item $[p_{(2n,n)}]X_{\trtn}=(-1)^{3n}(4n^2+6n-7)$ and
\item $[p_{(n^3)}]X_{\trtn}=(-1)^{3n-3}(3n-2)$.
\end{enumerate}
\label{lem:coeff_power_G_n,n,n}
\end{lemma}

\begin{proof}
To prove this we will use Lemma~\ref{lem:stanley} that considers all subsets of the edge set $E$. 
We are only interested in subsets $S\subseteq E$ that yield $\lambda(S)=(3n)$, $(2n,n)$ or $(n^3)$. Note that all of these have parts  at least $n$ so we will disregard any set $S$ where $\lambda(S)$ has a part smaller than $n$. If  $S$ has two or more edges removed from any of the $n$-paths, then $\lambda(S)$ certainly will have a part   smaller than $n$. Thus we will only consider subsets $S\subseteq E$ that have \emph{at most one edge} removed from any of the $n$-paths. 
In Table~\ref{table:G_n,n,noptions} we have considered all cases of $1$ through $5$ edges removed from the two triangles and have enumerated and collected all isomorphic graphs. This will be especially useful in our delicate case analysis, consisting of 7 cases corresponding to the removal of 0 to 6 edges from $E$. 

First, consider  $|S|=|E|$. This gives us the term $$(-1)^{3n+3}p_{(3n)}.$$ 

Second, consider $|S|=|E|-1$, and note that removing any one of the $3n+3$ edges yields a connected graph, and hence the term $$(-1)^{3n+2}(3n+3)p_{(3n)}.$$

Third, consider $|S|=|E|-2$. If the two removed edges come from the triangles there are  $15$ possibilities and we can see from Table~\ref{table:G_n,n,noptions} that all these possibilities are connected so contributes the term $(-1)^{3n+1}15p_{(3n)}$. 

Say we remove one edge from the triangles and one from the paths. In all 6 identical  possibilities of removing one edge from a triangle we can remove any one of the $3(n-1)$  edges from the $n$-paths and maintain a connected graph so we get the term  $(-1)^{3n+1}18(n-1)p_{(3n)}$. 

Next consider the situation where we remove two edges from the $n$-paths. We noted earlier that these two edges cannot be from the same $n$-path.  There are $\binom{3}{2}$ ways to choose the two $n$-paths and $n-1$ edge choices in each $n$-path. Since the resulting graph is always connected we have the term $(-1)^{3n+1}3(n-1)^2p_{(3n)}$. 

Altogether this case contributes the term $$(-1)^{3n+1}(3n^2+12n)p_{(3n)}.$$

Fourth, consider $|S|=|E|-3$. Now consider the situation of removing those three edges from the triangles. We can see from Table~\ref{table:G_n,n,noptions} that all $20$ possibilities are connected so contribute the term $(-1)^{3n}20p_{(3n)}$. 

Say instead we remove two edges from the triangles and one from the $n$-paths. In the 6 possibilities on the left in  Table~\ref{table:G_n,n,noptions} if we remove an edge from the left $n$-path we disconnect the graph yielding a part smaller than $n$. If instead we remove any one of the $2(n-1)$ edges from the middle or right $n$-paths, then we have a connected graph, which contributes the term $(-1)^{3n}12(n-1)p_{(3n)}$. In the remaining $9$ middle and right possibilities of removing two edges from the triangles  we can remove any one of the $3(n-1)$ edges from the three $n$-paths and still have a connected graph, which contributes the term $(-1)^{3n}27(n-1)p_{(3n)}$. 

Now say that we remove one edge from the triangle and two edges from the $n$-paths. Again, these two edges must be on different $n$-paths and any choice of edges on the two $n$-paths will leave the graph connected. With $6$ ways to remove an edge from the triangle, $\binom{3}{2}$ ways to choose the two $n$-paths, and $(n-1)^2$ ways to choose the edges on the $n$-paths we get the term $(-1)^{3n}18(n-1)^2p_{(3n)}$. 

Finally, consider the situation where we remove all three edges from the $n$-paths. No two of these removed edges are on the same $n$-path so we are removing one edge from each $n$-path. This will certainly disconnect the graph into two pieces. The only two-part partition we are interested in is $(2n,n)$ so we will count the edge removal choices that splits the graph yielding a partition of this type. We will first count the number of possibilities so that the piece connected to the top triangle has  $n$ vertices. Say  we remove an edge on the left $n$-path that results in $i$ vertices from this $n$-path contributing to this top connected piece. Also,  say we remove an edge from  the middle $n$-path so that the middle $n$-path contributes $j$ vertices to the top connected piece. As long as $1\leq i,j \leq n-1$ and $2\leq i+j\leq n-1$ then there exists exactly one edge in the right $n$-path that contributes $n-i-j$ vertices to the top connected piece, which yields our piece with $n$ vertices. The number of choices for $i$ and $j$ is  $\frac{(n-1)(n-2)}{2}$. Since there are equally many choices to instead make the bottom connected piece have $n$ vertices then this  contributes the term $(-1)^{3n}(n-1)(n-2)p_{(2n,n)}$. 

Altogether this case contributes the terms $$(-1)^{3n}(18n^2+3n-1)p_{(3n)}$$and $$(-1)^{3n}(n^2-3n+2)p_{(2n,n)}.$$ 

Fifth, consider $|S|=|E|-4$. There are $15$ possibilities for removing all four of the edges from the triangles. We can see in Table~\ref{table:G_n,n,noptions} that in $12$ of the possibilities the graph remains connected so contributes the term $(-1)^{3n-1}12p_{(3n)}$. In the remaining 3 possibilities the graph becomes an $n$-path and a $2n$-cycle so contributes the term $(-1)^{3n-1}3p_{(2n,n)}$. 

Next consider removing only three edges from the triangles and one edge from the $n$-paths. In the left $12$ possibilities listed in  Table~\ref{table:G_n,n,noptions} we can remove any of the $2(n-1)$ edges from the left and middle $n$-paths and maintain a connected graph.  The removal of any edge from the right $n$-path will yield a part smaller than $n$. In the middle $6$ possibilities listed in Table~\ref{table:G_n,n,noptions} we again can remove any one of the  $2(n-1)$ edges from the left or right $n$-path and maintain a connected graph, but choosing an edge from the middle $n$-path yields a part smaller than $n$.  In the right 2 possibilities in Table~\ref{table:G_n,n,noptions} any edge removed from any $n$-path would yield a part smaller than $n$ so altogether this contributes the term $(-1)^{3n-1}36(n-1)p_{(3n)}$. 

Next say we remove two edges from the triangles and two edges from the $n$-paths. In  Table~\ref{table:G_n,n,noptions} we can see for  the left $6$ possibilities that we can only remove the two edges from the  right and middle $n$-paths and this will split the graph into two pieces. Any choice of one of the $n-1$ edges from the middle $n$-path gives us precisely one choice for an edge in the right $n$-path so that we disconnect the graph to yield  $(2n,n)$. This contributes the term $(-1)^{3n-1}6(n-1)p_{(2n,n)}$. In the remaining 9 middle and right possibilities in Table~\ref{table:G_n,n,noptions} we can choose any two $n$-paths in $\binom{3}{2}$ ways and choose any edge in $(n-1)^2$ ways and still have a connected graph, which contributes the term $(-1)^{3n-1}27(n-1)^2p_{(3n)}$. 

Finally consider the situation when we remove only one edge from the triangles and three edges from the $n$-paths. Very similar to  earlier this breaks the graph into two pieces and there are $(n-1)(n-2)$ ways to choose the edges so that the graph is separated into one piece of size $2n$ and another of size $n$, which contributes the term $(-1)^{3n-1}6(n-1)(n-2)p_{(2n,n)}$. We cannot remove four edges from the $n$-paths else we yield a part smaller than $n$. 

Altogether this case contributes the terms $$(-1)^{3n-1}(27n^2-18n+3)p_{(3n)}$$and $$(-1)^{3n-1}(6n^2-12n+9)p_{(2n,n)}.$$

Sixth, consider $|S|=|E|-5$. If all five edges are removed from the triangles, then we have $6$ possibilities all of which give us a disconnected $n$-path and $2n$-path that contributes the term $(-1)^{3n-2}6p_{(2n,n)}$. 

Say we remove  four edges from the triangles and one from the $n$-paths. The left and middle 12 possibilities in  Table~\ref{table:G_n,n,noptions} will split the graph into two pieces, but not yielding the partition $(2n,n)$. In the right  3 possibilities in Table~\ref{table:G_n,n,noptions} we do not want to remove an edge from the left $n$-path since we would yield a part smaller than $n$, but we can remove any of the $2(n-1)$ other edges from the $n$-paths and  have the graph yield $(2n,n)$, which contributes the term $(-1)^{3n-2}6(n-1)p_{(2n,n)}$. 

Say we remove three edges from the triangles and two from the $n$-paths. In  Table~\ref{table:G_n,n,noptions} we can see with the right 2 possibilities that there is no choice of edges on the $n$-paths that  disconnects the graph yielding parts we are interested in. In the left and middle $18$ possibilities  there are two $n$-paths we can remove the two edges from without automatically yielding a part smaller than $n$. Also, any choice of edges on the $n$-paths splits the graph into two pieces so we need to count the possibilities that result in the partition $(2n,n)$. For any of the   $n-1$ choices for an edge on one $n$-path there is exactly one choice of an edge on the other $n$-path so we partition the graph  to yield $(2n,n)$. Together this contributes the term $(-1)^{3n-2}18(n-1)p_{(2n,n)}$. 

Finally, consider removing two edges from the triangles and three edges from the $n$-paths. 
 For the right and middle $9$ possibilities in Table~\ref{table:G_n,n,noptions} this splits the graph into two pieces and  there are $(n-1)(n-2)$ ways to choose the edges so that the graph is separated into a piece of size $2n$ and another of size $n$ as discussed earlier. In the left  $6$ possibilities in Table~\ref{table:G_n,n,noptions} we would split the graph so that it yields a part smaller than $n$. This contributes the term $(-1)^{3n-2}9(n-1)(n-2)p_{(2n,n)}$. Again, we cannot remove more than four edges from the $n$-paths else we yield a part smaller than $n$. 
 
Altogether this case gives us the term $$(-1)^{3n-2}(9n^2-3n)p_{(2n,n)}.$$

Seventh and finally, consider $|S|=|E|-6$. If we remove all six edges from the triangles we obtain   three disconnected $n$-paths, which contributes the term $(-1)^{3n-3}p_{(n^3)}$.

If we remove five edges from the triangles and one from the $n$-paths, then we can see that in all 6 possibilities in Table~\ref{table:G_n,n,noptions} we will split our graph into three pieces not yielding $(n,n,n)$. 

Say that we remove four edges from the triangles and two from the $n$-paths. In the left and middle 12 possibilities in Table~\ref{table:G_n,n,noptions} we will split the graph into pieces we are not interested in. In the right 3 possibilities in Table~\ref{table:G_n,n,noptions} we split the graph into three pieces and any one choice of the $n-1$ edges in the middle $n$-path will leave us with one choice of an edge in the right $n$-path so that we split our graph into three pieces of size $n$. This gives us the term $(-1)^{3n-3}3(n-1)p_{(n^3)}$. 

Say that we remove three edges from the triangles and three from the $n$-paths. In all 20 possibilities in Table~\ref{table:G_n,n,noptions} we split the graph into pieces of sizes we are not interested in. 

Since we cannot remove four or more edges from the $n$-paths and get pieces of size  at least $n$ altogether this case gives us the term $$(-1)^{3n-3}(3n-2)p_{(n^3)}.$$

No matter how we remove seven or more edges in total we will obtain a part smaller than $n$, so we have   considered all sets $S$ that contribute to the partitions $(3n)$, $(2n,n)$ and $(n^3)$. Adding everything  we get 
\begin{align*}[p_{(3n)}]X_{\trtn}&=(-1)^{3n+3}(1-(3n+3)+(3n^2+12n)-(18n^2+3n-1)+(27n^2-18n+3))\\&=(-1)^{3n+3}(12n^2-12n+2)\end{align*}and
\begin{align*}[p_{(2n,n)}]X_{\trtn}&=(-1)^{3n}((n^2-3n+2)-(6n^2-12n+9)+(9n^2-3n))\\&=(-1)^{3n}(4n^2+6n-7)\end{align*}and
\begin{align*}[p_{(n^3)}]X_{\trtn}&=(-1)^{3n-3}(3n-2).\end{align*}
\end{proof}


Similar to Lemma~\ref{lem:elemcoeffpower} we can prove the following.


\begin{lemma} For $n\geq 1$  we have that
\begin{enumerate}
\item $[e_{(n^3)}]p_{(3n)}=(-1)^{3n-3}n$,
\item $[e_{(n^3)}]p_{(2n,n)}=(-1)^{3n-3}n^2$ and
\item $[e_{(n^3)}]p_{(n^3)}=(-1)^{3n-3}n^3$.
\end{enumerate}
\label{lem:coeff_e[n,n,n]}
\end{lemma}

\begin{proof}
Using Equation~\eqref{eq:newton} we have that $[e_{(n^3)}]p_{(3n)}=(-1)^{3n-3}\frac{3n(3-1)!}{3!}=(-1)^{3n-3}n$. 

Recall from Lemma~\ref{lem:elemcoeffpower} and its proof that $[e_{(n^2)}]p_{(2n)}=(-1)^{2n-2}n$ and 
$[e_{n}]p_{n}=(-1)^{n-1}n$. In $p_{(n^3)}=p_np_np_n$ the coefficient of 
$e_{(n^3)}$ is purely determined by the multiplication of the coefficients of $e_{n}$ in  $p_n$, which gives 
$[e_{(n^3)}]p_{(n^3)}=([e_{n}]p_{n})^3=(-1)^{3n-3}n^3$. In $p_{(2n,n)}=p_{(2n)}p_n$ the coefficient of $e_{(n^3)}$ 
is purely determined by the multiplication of the coefficient of $e_{(n^2)}$ in  $p_{(2n)}$ and $e_{n}$ in  $p_{n}$, which gives $[e_{(n^3)}]p_{(2n,n)}=[e_{(n^2)}]p_{(2n)}[e_{n}]p_{n}=(-1)^{3n-3}n^2$. 
\end{proof}

\begin{lemma} The chromatic symmetric function of $\trtn$ for $n\geq3$ is not $e$-positive. In particular, we have that 
$$[e_{(n^3)}]X_{\trtn}=-n(n-1)^2(n-2).$$
\label{lem:trt_notepos}
\end{lemma}


\begin{proof}
By Observation~\ref{obs:newton} we can see that  $e_{(n^3)}$ has a non-zero coefficient in $p_{\lambda}$ only for  $\lambda\vdash 3n$ with $\lambda\coarsep (n^3)$. There are only three partitions $\lambda\vdash 3n$ where $\lambda\coarsep (n^3)$, namely $(3n)$, $(2n,n)$ and $(n^3)$. 

Since 
$$X_{\trtn}=\sum_{\lambda\vdash 3n}[p_{\lambda}]X_{\trtn} p_{\lambda}$$
the coefficient of $e_{(n^3)}$ in $X_{\trtn}$ only arises from the  $p_{(3n)}$, $p_{(2n,n)}$ and $p_{(n^3)}$ terms. In particular, 
$$[e_{(n^3)}]X_{\trtn}=[e_{(n^3)}]p_{(3n)}\cdot [p_{(3n)}]X_{\trtn}+[e_{(n^3)}]p_{(2n,n)}\cdot [p_{(2n,n)}]X_{\trtn}+[e_{(n^3)}]p_{(n^3)}\cdot[p_{(n^3)}]X_{\trtn}.$$
Using  Lemma~\ref{lem:coeff_power_G_n,n,n} and Lemma~\ref{lem:coeff_e[n,n,n]}  we therefore have
\begin{align*}
[e_{(n^3)}]X_{\trtn}&=n\cdot(12n^2-12n+2)-n^2\cdot(4n^2+6n-7)+n^3\cdot(3n-2)\\
&=-n(n-1)^2(n-2).
\end{align*}
%\begin{align*}
%[e_{(n^2)}]X_{G_{n,n}}&=(-1)^{3n-3}n^3\cdot (-1)^{3n-3}(3n-2)
%+(-1)^{3n-3}n^2\cdot (-1)^{3n}(4n^2+6n-7)\\
%&\hspace{.2in}+(-1)^{3n-3}n\cdot (-1)^{3n+3}(12n^2-12n+2)\\
%&=-n(n-1)^2(n-2).
%\end{align*}
\end{proof}

%%%SAM END 2

We can now identify our third family of graphs that are \ccf, are furthermore claw-free, and whose chromatic symmetric functions are not $e$-positive.

\begin{theorem}\label{the:trtnotpositive} The graphs $\trtn$ for all $n\geq 3$ are \ccf, claw-free and not $e$-positive.
\end{theorem}

\begin{proof} This follows immediately from Lemmas~\ref{lem:trt_ccf} and \ref{lem:trt_notepos}.
\end{proof}

\begin{remark}\label{rem:inc} One might ask whether triangular tower graphs are also incomparability graphs, so as to also potentially be a counterexample to Stanley's $(\mbox{\textbf{3}}+\mbox{\textbf{1}})$-free conjecture \cite[Conjecture 5.1]{Stan95}. However, it is straightforward to check that triangular tower graphs are not incomparability graphs.
\end{remark}

We conclude by conjecturing that the triangular tower graphs $\trtn$ for $n\geq 3$ are in some sense a minimal family of graphs that are \ccf, claw-free and whose chromatic symmetric functions are not $e$-positive. More precisely we conjecture that there do not exist graphs with 10 or 11 vertices that are  \ccf, claw-free and whose chromatic symmetric functions are not $e$-positive.




\section*{Acknowledgements}\label{sec:acknow} The authors would like to thank Omar Antol\'{i}n Camarena and Jair Taylor for sharing their code, which we incorporated into ours when generating our extensive data sets in Sage \cite{Sage}. They would also like to thank Miki Racz for translating \cite[Theorem 1]{Krausz} and Richard Stanley for supportive conversations. All three authors were supported  in part by the National Sciences and Engineering Research Council of Canada. This work was supported by the Canadian Tri-Council Research Support Fund. 
%: Bibliography


\def\cprime{$'$}
\begin{thebibliography}{10}



\bibitem{Jose2} J.~Aliste-Prieto and J.~Zamora, Proper caterpillars are distinguished by their chromatic symmetric function, \emph{Discrete Math.} 315, 158--164 (2014).

\bibitem{Ath} C.~Athanasiadis, Power sum expansion of chromatic quasisymmetric
functions, \emph{Electron. J. Combin.} 22, Paper 2.7 9pp (2015).

\bibitem{Beineke} L.~Beineke,  Characterizations of derived graphs, \emph{J. Combin. Theory} 9, 129--135 (1970).

\bibitem{Benedetti} C.~Benedetti, J.~Hallam and J.~Machacek, Combinatorial Hopf algebras of simplicial complexes, \emph{SIAM J. Discrete Math.} to appear.

\bibitem{BJR} L.~Billera, N.~Jia and V.~Reiner, A quasisymmetric function for
  matroids, 
  \emph{European J. Combin.} 30, 1727--1757 (2009).

\bibitem{Birkhoff} G.~Birkhoff, A determinant formula for the number of ways of coloring a map, \emph{Ann. of Math.} 14, 42--46
(1912).


  
\bibitem{BK}  F.~Breuer and C.~Klivans, Scheduling problems, \emph{J. Combin. Theory Ser. A} 139, 59--79 (2016).

\bibitem{BrosnanC} P.~Brosnan and T.~Chow, Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties,
{\tt arXiv:1511.00773}

\bibitem{BV} A.~Brouwer and H.~Veldman,  Contractibility and NP-completeness, \emph{J. Graph Theory} 11, 71--79 (1987).

\bibitem{Bryl} T.~Brylawski, Intersection theory for graphs, \emph{J. Combin. Theory Ser. B} 
30, 233--246 (1981).

\bibitem{Carlitz} L.~Carlitz, R.~Scoville and T.~Vaughan, Enumeration of pairs of
sequences by rises, falls and levels, \emph{Manuscripta Math.} 19,
211--243 (1976).

\bibitem{Cauchy}
 A.~Cauchy, {M\'{e}moire sur les fonctions qui ne peuvent obtenir que deux valeaurs \'{e}gale et de signes contraires par suite des transpositions op\'{e}r\'{e}s entre les variables qu'elles renferment}, 
\emph{J. \'Ec. Polytech.} 10,
   29--112 (1815).

\bibitem{Clearman} S.~Clearman, M.~Hyatt, B.~Shelton and M.~Skandera, Evaluations
of Hecke algebra traces at Kazhdan-Lusztig basis elements, \emph{Electron. J. Combin.} 23, Paper 2.7 56pp (2016).


\bibitem{Gasharov} V.~Gasharov, Incomparability graphs of $(3 + 1)$-free posets are
$s$-positive, \emph{Discrete Math.} 157, 193--197 (1996).

\bibitem{Gash} V.~Gasharov, On Stanley's chromatic symmetric function and clawfree graphs, \emph{Discrete Math.} 205, 229--234 (1999).

\bibitem{GebSag} D.~Gebhard and B.~Sagan,  A chromatic symmetric function in noncommuting variables, \emph{J. Algebraic Combin.} 13, 227--255 (2001). 

\bibitem{GP} M.~Guay-Paquet, A modular law for the chromatic symmetric functions of $(3+1)$-free posets, {\tt arXiV:1306.2400v1}

  \bibitem{Humpert} B.~Humpert,
A quasisymmetric function generalization of the chromatic symmetric function, 
\emph{ Electron. J. Combin.}
18,
Paper 31 13pp (2011).

\bibitem{Kaliz} R.~Kaliszewski, Hook coefficients of chromatic functions, \emph{J. Comb.} 6, 327--337 (2015). 

\bibitem{Klazar} M.~Klazar, M.~Loebl and I.~Moffatt, The Potts model and chromatic functions of graphs, \emph{Ann. Inst. Henri Poincar\'{e} D} 1, 47--60 (2014).

\bibitem{Kratt} C.~Krattenthaler, Combinatorial proof of the log-concavity
of the sequence of matching numbers, \emph{J. Combin. Theory Ser. A} 74, 351--354 (1996).

\bibitem{Krausz} J.~Krausz, Egy Whitney-f\'{e}le gr\'{a}f-t\'{e}tel \'{u}j bizony\'{i}t\'{a}sa,
\emph{Mat. Fiz. Lapok} 50, 75--85 (1943).

  \bibitem{MacD} I.~Macdonald, Symmetric functions and Hall polynomials. 2nd ed.,
 {Oxford University Press}, 1998.


\bibitem{MMW} J.~Martin, M.~Morin and J.~Wagner, On distinguishing trees by their chromatic symmetric
functions, \emph{J. Combin. Theory Ser. A} 115, 237--253 (2008).

\bibitem{Noble} S.~Noble and D.~Welsh, A weighted graph polynomial from chromatic invariants of knots, \emph{Ann. Inst. Fourier (Grenoble)} 49, 1057--1087  (1999).

\bibitem{Orellana} R.~Orellana and G.~Scott, Graphs with equal chromatic symmetric function, \emph{Discrete Math.} 320, 1--14 (2014).

\bibitem{Paunov1}A.~Paunov,  Planar graphs and Stanley's chromatic functions, {\tt arXiv:1702.05787}


    
    \bibitem{Paunov2}   A.~Paunov and A.~Szenes, A new approach to $e$-positivity for Stanley's chromatic functions,  {\tt arXiv:1702.05791}


\bibitem{vRW} A.~van Rooij and H. Wilf, The interchange graph of a finite graph, \emph{Acta Math. Acad. Sci. Hungar. }16, 263--269  (1965).

\bibitem{Sagan} B.~Sagan, {{The symmetric group. Representations, combinatorial
  algorithms, and symmetric functions. 2nd ed.}}, Springer, 2001.
  
  \bibitem{Sage} SageMath, The Sage mathematics software system (Version 7.5.1),
   The Sage Developers, 2017, {\tt http://www.sagemath.org}
  
  \bibitem{Sarm} I.~Sarmiento, The polychromate and a chord diagram polynomial, \emph{Ann. Comb.} 4, 227--236 (2000).

\bibitem{SW} J.~Shareshian and M.~Wachs, Chromatic quasisymmetric functions, \emph{Adv. Math.} to appear.

\bibitem{Stan95} R.~Stanley, A symmetric function generalization of the chromatic polynomial of a graph, \emph{Adv. Math.} 111, 166--194 (1995).

\bibitem{Stan_AG} R.~Stanley, Graph colorings and related symmetric functions: ideas and applications,
\emph{Discrete Math.} 193, 267--286 (1998).

  \bibitem{ECII}R.~Stanley,  {Enumerative
  Combinatorics} vol.~2, Cambridge University Press, 1999.

\bibitem{StanStem} R.~Stanley and J.~Stembridge, On imminants of Jacobi-Trudi matrices and permutations with restricted position, \emph{J. Combin. Theory Ser. A} 62, 261--279 (1993).

\bibitem{SWW} T.~Sundquist, D.~Wagner and J.~West, 
A Robinson-Schensted algorithm for a class of partial orders, \emph{J. Combin. Theory Ser. A} 79, 36--52 (1997).

\bibitem{Wolfe} M.~Wolfe, Symmetric chromatic functions, \emph{Pi Mu Epsilon Journal} 10, 643--757 (1998).

\end{thebibliography}


\end{document}
%%%%END

\bibitem{Chow} T.~Chow, Descents, quasi-symmetric functions, Robinson-Schensted for posets, and the chromatic symmetric function, \emph{J. Algebraic Combin.} 10, 227--240 (1999).

\bibitem{SagLee} J.~Lee and B.~Sagan, An algorithmic sign-reversing involution for special rim-hook tableaux, \emph{J. Algorithms} 59, 149--161 (2006).



\bibitem{Jonasson} J.~Jonasson, Lollipop graphs are extremal for commute times, \emph{Random Structures  Algorithms} 16, 131--142 (2000).

\bibitem{Jose2+1} J.~Aliste-Prieto, A.~de Mier and J.~Zamora, On trees with the same restricted U-polynomial and the Prouhet-Tarry-Escott problem, \emph{Discrete Math.} to appear.

\bibitem{BW} G.~Brightwell and P.~Winkler,  Maximum hitting time for random walks on graphs, \emph{Random Structures  Algorithms} 1, 263--276 (1990).

\bibitem{ChovW} S.~Cho and S.~van Willigenburg, Chromatic bases for symmetric functions, \emph{Electron. J. Combin.} 23, P1.15 6pp (2016).

\bibitem{Feige} U.~Feige, A tight upper bound on the cover time for random walks on graphs, \emph{Random Structures  Algorithms} 6, 51--54 (1995).

  \bibitem{Derksen} 
{\sc H.~Derksen},
{\em Symmetric and quasi-symmetric functions associated to polymatroids},
J. Algebraic Combin.
30 (2009)
 43--86.
1703.05770.extracted_bib
{Jose2 J.~Aliste-Prieto and J.~Zamora, Proper caterpillars are distinguished by their chromatic symmetric function, Discrete Math. 315, 158--164 (2014).
1703.05770.extracted_bib
{Ath C.~Athanasiadis, Power sum expansion of chromatic quasisymmetric functions, Electron. J. Combin. 22, Paper 2.7 9pp (2015).
1703.05770.extracted_bib
{Beineke L.~Beineke, Characterizations of derived graphs, J. Combin. Theory 9, 129--135 (1970).
1703.05770.extracted_bib
{Benedetti C.~Benedetti, J.~Hallam and J.~Machacek, Combinatorial Hopf algebras of simplicial complexes, SIAM J. Discrete Math. to appear.
1703.05770.extracted_bib
{BJR L.~Billera, N.~Jia and V.~Reiner, A quasisymmetric function for matroids, European J. Combin. 30, 1727--1757 (2009).
1703.05770.extracted_bib
{Birkhoff G.~Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. 14, 42--46 (1912).
1703.05770.extracted_bib
{BK F.~Breuer and C.~Klivans, Scheduling problems, J. Combin. Theory Ser. A 139, 59--79 (2016).
1703.05770.extracted_bib
{BrosnanC P.~Brosnan and T.~Chow, Unit interval orders and the dot action on the cohomology of regular semisimple Hessenberg varieties, {\tt arXiv:1511.00773
1703.05770.extracted_bib
{BV A.~Brouwer and H.~Veldman, Contractibility and NP-completeness, J. Graph Theory 11, 71--79 (1987).
1703.05770.extracted_bib
{Bryl T.~Brylawski, Intersection theory for graphs, J. Combin. Theory Ser. B 30, 233--246 (1981).
1703.05770.extracted_bib
{Carlitz L.~Carlitz, R.~Scoville and T.~Vaughan, Enumeration of pairs of sequences by rises, falls and levels, Manuscripta Math. 19, 211--243 (1976).
1703.05770.extracted_bib
{Cauchy A.~Cauchy, {M\'{emoire sur les fonctions qui ne peuvent obtenir que deux valeaurs \'{egale et de signes contraires par suite des transpositions op\'{er\'{es entre les variables qu'elles renferment, J. \'Ec. Polytech. 10, 29--112 (1815).
1703.05770.extracted_bib
{Clearman S.~Clearman, M.~Hyatt, B.~Shelton and M.~Skandera, Evaluations of Hecke algebra traces at Kazhdan-Lusztig basis elements, Electron. J. Combin. 23, Paper 2.7 56pp (2016).
1703.05770.extracted_bib
{Gasharov V.~Gasharov, Incomparability graphs of $(3 + 1)$-free posets are $s$-positive, Discrete Math. 157, 193--197 (1996).
1703.05770.extracted_bib
{Gash V.~Gasharov, On Stanley's chromatic symmetric function and clawfree graphs, Discrete Math. 205, 229--234 (1999).
1703.05770.extracted_bib
{GebSag D.~Gebhard and B.~Sagan, A chromatic symmetric function in noncommuting variables, J. Algebraic Combin. 13, 227--255 (2001).
1703.05770.extracted_bib
{GP M.~Guay-Paquet, A modular law for the chromatic symmetric functions of $(3+1)$-free posets, {\tt arXiV:1306.2400v1
1703.05770.extracted_bib
{Humpert B.~Humpert, A quasisymmetric function generalization of the chromatic symmetric function, Electron. J. Combin. 18, Paper 31 13pp (2011).
1703.05770.extracted_bib
{Kaliz R.~Kaliszewski, Hook coefficients of chromatic functions, J. Comb. 6, 327--337 (2015).
1703.05770.extracted_bib
{Klazar M.~Klazar, M.~Loebl and I.~Moffatt, The Potts model and chromatic functions of graphs, Ann. Inst. Henri Poincar\'{e D 1, 47--60 (2014).
1703.05770.extracted_bib
{Kratt C.~Krattenthaler, Combinatorial proof of the log-concavity of the sequence of matching numbers, J. Combin. Theory Ser. A 74, 351--354 (1996).
1703.05770.extracted_bib
{Krausz J.~Krausz, Egy Whitney-f\'{ele gr\'{af-t\'{etel \'{uj bizony\'{it\'{asa, Mat. Fiz. Lapok 50, 75--85 (1943).
1703.05770.extracted_bib
{MacD I.~Macdonald, Symmetric functions and Hall polynomials. 2nd ed., {Oxford University Press, 1998.
1703.05770.extracted_bib
{MMW J.~Martin, M.~Morin and J.~Wagner, On distinguishing trees by their chromatic symmetric functions, J. Combin. Theory Ser. A 115, 237--253 (2008).
1703.05770.extracted_bib
{Noble S.~Noble and D.~Welsh, A weighted graph polynomial from chromatic invariants of knots, Ann. Inst. Fourier (Grenoble) 49, 1057--1087 (1999).
1703.05770.extracted_bib
{Orellana R.~Orellana and G.~Scott, Graphs with equal chromatic symmetric function, Discrete Math. 320, 1--14 (2014).
1703.05770.extracted_bib
{Paunov1A.~Paunov, Planar graphs and Stanley's chromatic functions, {\tt arXiv:1702.05787
1703.05770.extracted_bib
{Paunov2 A.~Paunov and A.~Szenes, A new approach to $e$-positivity for Stanley's chromatic functions, {\tt arXiv:1702.05791
1703.05770.extracted_bib
{vRW A.~van Rooij and H. Wilf, The interchange graph of a finite graph, Acta Math. Acad. Sci. Hungar. 16, 263--269 (1965).
1703.05770.extracted_bib
{Sagan B.~Sagan, {{The symmetric group. Representations, combinatorial algorithms, and symmetric functions. 2nd ed., Springer, 2001.
1703.05770.extracted_bib
{Sage SageMath, The Sage mathematics software system (Version 7.5.1), The Sage Developers, 2017, {\tt http://www.sagemath.org
1703.05770.extracted_bib
{Sarm I.~Sarmiento, The polychromate and a chord diagram polynomial, Ann. Comb. 4, 227--236 (2000).
1703.05770.extracted_bib
{SW J.~Shareshian and M.~Wachs, Chromatic quasisymmetric functions, Adv. Math. to appear.
1703.05770.extracted_bib
{Stan95 R.~Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Adv. Math. 111, 166--194 (1995).
1703.05770.extracted_bib
{Stan_AG R.~Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Math. 193, 267--286 (1998).
1703.05770.extracted_bib
{ECIIR.~Stanley, {Enumerative Combinatorics vol.~2, Cambridge University Press, 1999.
1703.05770.extracted_bib
{StanStem R.~Stanley and J.~Stembridge, On imminants of Jacobi-Trudi matrices and permutations with restricted position, J. Combin. Theory Ser. A 62, 261--279 (1993).
1703.05770.extracted_bib
{SWW T.~Sundquist, D.~Wagner and J.~West, A Robinson-Schensted algorithm for a class of partial orders, J. Combin. Theory Ser. A 79, 36--52 (1997).
1703.05770.extracted_bib
{Wolfe M.~Wolfe, Symmetric chromatic functions, Pi Mu Epsilon Journal 10, 643--757 (1998).
1703.05770.extracted_bib
{Chow T.~Chow, Descents, quasi-symmetric functions, Robinson-Schensted for posets, and the chromatic symmetric function, J. Algebraic Combin. 10, 227--240 (1999).
1703.05770.extracted_bib
{SagLee J.~Lee and B.~Sagan, An algorithmic sign-reversing involution for special rim-hook tableaux, J. Algorithms 59, 149--161 (2006).
1703.05770.extracted_bib
{Jonasson J.~Jonasson, Lollipop graphs are extremal for commute times, Random Structures Algorithms 16, 131--142 (2000).
1703.05770.extracted_bib
{Jose2+1 J.~Aliste-Prieto, A.~de Mier and J.~Zamora, On trees with the same restricted U-polynomial and the Prouhet-Tarry-Escott problem, Discrete Math. to appear.
1703.05770.extracted_bib
{BW G.~Brightwell and P.~Winkler, Maximum hitting time for random walks on graphs, Random Structures Algorithms 1, 263--276 (1990).
1703.05770.extracted_bib
{ChovW S.~Cho and S.~van Willigenburg, Chromatic bases for symmetric functions, Electron. J. Combin. 23, P1.15 6pp (2016).
1703.05770.extracted_bib
{Feige U.~Feige, A tight upper bound on the cover time for random walks on graphs, Random Structures Algorithms 6, 51--54 (1995).