\section{Background and main results}


 The Tutte polynomial is a universal
polynomial invariant defined on a graph which obeys a particular recurrence relation for the contraction and deletion of the edges of this graph. This universal property turns out
to have several implications in particular  
in statistical mechanics \cite{sok}. The Bollobas-Riordan (BR) polynomial \cite{bollo}  defines an authentic extension of the Tutte polynomial for simple graphs \cite{tutte} to ribbon graphs or neighborhoods of graphs 
embedded in surfaces. 

In this work, we investigate a family of graphs 
for which both the Tutte and BR polynomial invariants find
a meaningful extension. The family of such graphs are issued from the so-called colored tensor graphs representing simplicial complexes
in any dimension $D$ \cite{Gurau:2009tw}. The present study 
is mainly addressed for $D=3$, although, at the beginning 
and for the sake of generality, we carry out the analysis
for any dimension $D$. We focus on $D=3$ 
because we aim at making a first step towards the definition of a universal polynomial invariant precisely of the Tutte or BR form for 
particular graphs having a (3D) volume which is still 
missing to the best of our knowledge. 

It can be underlined that the graphs that we shall study are
somehow recently found. They naturally appear as Feynman graphs
 in a particular quantum field theoretical framework called colored tensor field theory introduced by Gurau \cite{Gurau:2009tw}\cite{Gurau:2009tz}
and further investigated afterwards \cite{Gurau:2010nd, Geloun:2009pe,sefu3,Gurau:2011xp}. 
For a version of these graphs without color, we refer the reader to more references therein.  According to quantum field procedures, these graphs can be dually associated with gluing of basic $D$ simplexes (vertices) along their faces or $D-1$ boundary simplexes (propagators or edges). 
 The graphs in question are called stranded and can be depicted in a 
three dimensional space. Fields in this framework are rank $D$ tensors. Hence the notion of (tensor) rank and 
the dimension of the space generated by the gluing are related. 
We shall not distinguish these in the following. 

There are two main contributions  addressing 
 an extension of the BR polynomial 
for a similar family of graphs that will be presented here:
the contribution by Gurau \cite{Gurau:2009tz} and the one
by Tanasa \cite{Tanasa:2010me}. 
Let us recall that for tensor graphs, the vertex is stranded and the simplest way of contracting an edge  leads immediately to another type of vertex which differs from the initial. As a consequence, the simplest prescriptions of contracting and deleting edges are not well defined without any further considerations. And indeed, the two aforementioned 
works undertake the definition of the contraction and deletion
of edges in a very peculiar manner. 

There are several layers of difficulties in order to obtain the correct 
definition of the type of graphs that ought to be considered, 
the type of topological polynomial defined for this family of graphs and
the type of recurrence relations that the polynomial needs to satisfy. 
Our method is radically different from that of Tanasa 
since we will use the Gurau colored prescription in order to 
have a control on the type of graphs that could be generated. 
Moreover, and in contrast with the work by Gurau, 
we propose to enlarge the family of graphs from the colored tensor
graphs to what will be called  weakly-colored (w-colored) stranded graphs
for which contraction and a similar notion of deletion
make a sense. 
 Strictly speaking these w-colored stranded graphs 
are equivalence  classes of graphs. 
Within these classes, the contraction operation becomes stable
in some sense. From this stability, we can define a polynomial containing all specific data pertaining to the extended dimension 3 and the associated cellular decomposition of the graph.  We can establish as well a recurrence relation
satisfied by the new polynomial for w-colored stranded graphs.

Our main result appears in  Theorem \ref{theo:contens} of Section \ref{sect:tgraph}. 
This statement successfully determines the contraction and cut rule (an operation intuitively clear which replaces the deletion) with respect to an edge that should be fulfilled by a new polynomial spelled out in Definition \ref{def:topotens}. The representatives of the 
equivalence class of graphs on which the polynomial is defined
have several topological ingredients. Some of these ingredients 
will be introduced step by step in the following program as they turn out to be well defined for simple graphs
and ribbon graphs. 

A first ingredient is captured by the notion of flag \cite{tutte} which
can be introduced at the simplest graph level. 
This analysis is the purpose of Section \ref{sect:gratu}.
Theorem \ref{theo:contutefla} yields another interesting 
result of this work since it mainly establishes that
the Tutte polynomial for graphs with flags satisfies 
the universal equations of the Tutte polynomial. 
This point is original, to our knowledge, since it proves
that the universal equations for the Tutte polynomial with 
particular weights, apart from their more general meaning 
and usefulness in statistical mechanics \cite{bollo3}, 
can be found as equations for simple  graphs decorated 
with flags. 

A second key notion is that of open and closed
faces of a graph which can be already introduced  for
ribbon graphs. The consequences that open and closed faces
in a ribbon graph have on the related 
BR polynomial are addressed in Section \ref{sect:ribbonbollo}. 
Theorem \ref{theo:BRext} is another partial important 
contributing in establishing our final result.
We emphasize that in the work by Krajewski and co-workers \cite{krf}
ribbon graphs with flags and their topological polynomial 
 have been introduced in a different manner (the notion of open
faces is definitely absent therein, for instance). 
These authors used the framework of the partial or Chmutov
duality \cite{schmu} for establishing several interesting results
pertaining to ribbon graphs with flags. 
Our approach is more ``conventional'' and much in the spirit 
of the contribution \cite{bollo}. Thus, as far as we are 
concerned with ribbon graph flags and to the extent
of this work, Theorem \ref{theo:BRext} is new and explicitly describes
the implications that might have flags on the BR polynomial. 
 
A closing appendix provides explicit examples of the polynomial obtained 
for typical graphs.  




\section{Graphs and Tutte polynomial}
\label{sect:gratu}

This section starts the review of the main theorem 
that we aim to generalize in the next sections. 



\subsection{Graphs}

We review basic definitions for graphs (called sometimes simple graphs in the following) and their Tutte polynomial \cite{tutte,bollo3,riv}.  


\begin{definition}[Graph \cite{tutte}] \label{def:graph}
	A graph $\mathcal{G}$ is defined by a set $\mathcal{V}$ of vertices and a set $\mathcal{E}$ of edges  and a relation of incidence which associates with each edge 
either one or two vertices called its ends. 
We denote it as $\mathcal{G}(\mathcal{V},\mathcal{E})$ or simply $\mathcal{G}$. 
\end{definition}

\begin{definition}[Edges and terminal forms \cite{tutte}\cite{riv}] 
\label{def:edg}

	Let $e$ be an edge of a graph $\mathcal{G}$.

$\bullet$ $e$ is called a self-loop in $\mathcal{G}$ if the two ends of $e$ are adjacent to the same vertex $v$ of $\mathcal{G}.$

$\bullet$ $e$ is called a bridge in $\mathcal{G}$ if its removal disconnects a component of $\mathcal{G}.$

$\bullet$ $e$ is called an ordinary or regular edge of $\mathcal{G}$ if it is neither a bridge nor a self-loop.

$\bullet$ A graph which does not contain any regular edge 
is called a terminal form.

\end{definition}


\begin{definition}[Deletion and contraction \cite{tutte},  Chap. I and II] \label{def:contdel}
Let $\mathcal{G}$ be a graph and $e$ one of its edges. 

$\bullet$ We call $\mathcal{G}-e$ the graph obtained from 
$\mathcal{G}$ by removing $e$. 


$\bullet$ If $e$ is not a self-loop, the  graph $\mathcal{G}/e$  obtained by contracting $e$ is defined from $\mathcal{G}$ by deleting $e$ and 
identifying its end vertices into a new vertex. 

$\bullet$ If $e$ is a self-loop, $\mathcal{G}/e$ is by definition the same as $\mathcal{G}-e.$
\end{definition}

One notices that after an arbitrary full contraction-deletion of 
regular edges of a given graph the end result is necessarily given by a collection of graphs composed by  bridges and/or self-loops, hence 
a terminal form. 


\begin{definition}[Subgraphs, spanning subgraphs  \cite{tutte}] \label{span}


$\bullet$ A subgraph $A$ of $\mathcal{G}(\mathcal{V},\mathcal{E})$ is defined as a graph $A(\mathcal{V}_A,\mathcal{E}_A)$ the vertex set of which is a subset of $\mathcal{V}$
and 
the edge set of which is a subset of $\mathcal{E}$ together with their end vertices.  Hence, $\mathcal{E}_A \subseteq \mathcal{E}$ and
$\mathcal{V}_A \subseteq \mathcal{V}$ and we denote $A \subseteq \mathcal{G}$.

$\bullet$ A spanning subgraph $A$ of $\mathcal{G}(\mathcal{V},\mathcal{E})$ is defined as   a subgraph $A(\mathcal{V}_A,\mathcal{E}_A)$ of $\mathcal{G}$ with all vertices of $\mathcal{G}$. 
Hence $\mathcal{E}_A\subseteq \mathcal{E}$ and $\mathcal{V}_A = \mathcal{V}$ and we denote
$A \Subset \mathcal{G}$. 
 
\end{definition}

\begin{definition}[Graph operations \cite{tutte}\cite{bollo}]
 \label{def:grop}

Consider two disjoint graphs $\mathcal{G}_1(\mathcal{V}_1,\mathcal{E}_1)$ and
$\mathcal{G}_2(\mathcal{V}_2,\mathcal{E}_2)$. We define 

$\bullet$ The disjoint union graph 
$\mathcal{G}_1 \sqcup \mathcal{G}_2$ as the graph defined by 
the disjoint union of the two graphs; 

$\bullet$ The product graph $\mathcal{G}_1 \cdot _{v_1,v_2} \mathcal{G}_2$ of the two graphs  simply merges at the vertices $v_1 \in \mathcal{V}_1$ and $v_2 \in \mathcal{V}_2$
the two graphs by removing $v_1$ and $v_2$ and 
insert a new vertex $v$ which has all edges incident 
to $v_1$ and to $v_2$. 

\end{definition}

Note that if a graph $\mathcal{G}$ can be written as $\mathcal{G}_1 \cdot _{v_1,v_2} \mathcal{G}_2$, this also means that  
$\mathcal{G}$ is one-to-one with  $\mathcal{G}_1 \sqcup \mathcal{G}_2$ 
(we will come back on this bijection later). 
It is simple to check that $A \Subset \mathcal{G}_1 \sqcup \mathcal{G}_2$ can be written as $A_1 \sqcup A_2$, where $A_i \Subset \mathcal{G}_i$. A similar relation holds for subgraphs $A \subset \mathcal{G}_1 \sqcup \mathcal{G}_2$. Idem,   $A \Subset \mathcal{G}_1 \cdot _{v_1,v_2}
\mathcal{G}_2$ implies that $A= A_1 \cdot _{v_1,v_2} A_2$ where $A_i \Subset \mathcal{G}_i$. However such a relation holds for subgraphs of $\mathcal{G}_1 \cdot _{v_1,v_2}\mathcal{G}_2$ only if each $A_i \subset \mathcal{G}_i$ contains
the vertex $v_i$.


We are now in position to define the Tutte polynomial
and specify its main properties. 

\begin{definition}[Tutte polynomial 1 \cite{bollo}\cite{riv}] \label{def:tutexp}
Let $\mathcal{G}(\mathcal{V},\mathcal{E})$ be a graph, then the Tutte polynomial $T_{\mathcal{G}}$ 
of $\mathcal{G}$ admits the following expansion:
\begin{equation}
    T_{\mathcal{G}}(x,y)=\sum_{A\Subset \mathcal{G}}(x-1)^{{\rm r}\,(\mathcal{G})-{\rm r}\, (A)}(y-1)^{n(A)},
\label{tutexp}
\end{equation}
    where ${\rm r}\,(A)=|\mathcal{V}|-k(A)$ is the rank of the spanning subgraph $A$, 
$k(A)$ its number of connected component 
and $n(A)=|A|+k(A)-|\mathcal{V}|$ is its nullity or cyclomatic number.
\end{definition}
There is an equivalent definition of this polynomial. 
\begin{definition}[Tutte polynomial 2 \cite{bollo3}] \label{def:tutrec}
Let $\mathcal{G}(\mathcal{V},\mathcal{E})$ be a graph.
The Tutte polynomial of $\mathcal{G}$ denoted
$T_{\mathcal{G}}(x,y)$ is defined in the following way:

$\bullet$ If $\mathcal{G}$ has no edges, then $T_{\mathcal{G}}(x,y)=1.$

 Otherwise, for any edge $e\in \mathcal{E}$
    
$\bullet$ $T_{\mathcal{G}}(x,y)=T_{\mathcal{G}-e}(x,y) + T_{\mathcal{G}/e}(x,y)$, if $e$ is a regular edge.

$\bullet$ $T_{\mathcal{G}}(x,y)=xT_{\mathcal{G}-e}(x,y) = x T_{\mathcal{G}/e}$, if $e$ is a bridge.

$\bullet$ $T_{\mathcal{G}}(x,y)=yT_{\mathcal{G}-e}(x,y)=y T_{\mathcal{G}/e}(x,y)$, if $e$ is a self-loop.
\end{definition}

Some comments are in order at this point. 

(1) In several works, the variable $(y-1)$ appearing in \eqref{tutexp}
is replaced simply by $y$\footnote{Using $y$ 
instead of $(y-1)$ leads to non negative coefficients of the polynomial
\cite{bollo}.}.
The above convention  (for instance used in \cite{riv}) is simpler for the
following reason. In order to compute the 
Tutte polynomial of $\mathcal{G}$, one performs a full contraction and deletion
of regular edges of this graph which yields terminal forms. The Tutte polynomial of $\mathcal{G}$ is obtained by summing the contributions of its terminal forms. 
According to the above convention, $(x-1)$ and $(y-1)$, for a terminal form composed with $m$ bridges and $p$ self-loops, the Tutte polynomial is $x^m y^p$.

 (2)
By definition,  for a self-loop $e$, $\mathcal{G}-e=\mathcal{G}/e$
hence $T_{\mathcal{G}-e}= T_{\mathcal{G}/e}$ holds. It is however not trivial 
to prove that, for a bridge $e$, $T_{\mathcal{G}-e} = T_{\mathcal{G}/e}$ holds. 
A way to agree with this is to remark that 
$\mathcal{G}-e = \mathcal{G}_1 \sqcup \mathcal{G}_2$ and 
$\mathcal{G}/e = \mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2$
where $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are the two 
maximal\footnote{These graphs are maximal in the sense that 
they contain all vertices and all lines on a given side of the bridge.} subgraphs on each side of the bridge and $v_1$ and
$v_2$ are the end vertices of $e$. The claim $T_{\mathcal{G}-e}= T_{\mathcal{G}/e}$
is a direct consequence of the next proposition
following from the additivity property of the 
rank and the nullity with respect to the disjoint union and
product operations for graphs which implies a term by term
monomial factorization. 
\begin{proposition}[Operations on Tutte polynomial 1 \cite{tutte}]\label{optu} 
Let $\mathcal{G}_1$ and $\mathcal{G}_2$ be two disjoint graphs, then 
\begin{eqnarray} 
T_{\mathcal{G}_1 \sqcup \mathcal{G}_2}= T_{\mathcal{G}_1} T_{\mathcal{G}_2} = T_{\mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2}\,. 
\label{cups0}
\end{eqnarray}
for any  vertices $v_{1,2}$ in $\mathcal{G}_{1,2}$, respectively. 
\end{proposition}


\subsection{Graphs with  flags}
\label{subsec:tufla}

There exists a notion of ``decorated'' graph
encompassing the above graph consideration. 
This new category includes graphs  with flags 
or half-edges \cite{riv} hooked to vertices.


\begin{definition}[Flag] \label{def:fla}
A flag or half-edge (or half-line) is a line 
incident to a unique vertex and without forming a loop. 
(See Figure \ref{fig:flag}.) 
\end{definition}

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=1cm, height=0.1cm]{flag.pdf}
\caption{ {\small A flag incident to a unique vertex. }}
\label{fig:flag}
\end{minipage}
\end{figure}
\begin{definition}[Cut of an edge \cite{riv}] \label{def:cut}
Let $e \in \mathcal{E}$ be an edge of $\mathcal{G}(\mathcal{V},\mathcal{E})$. The cut graph 
$\mathcal{G}\vee e$ is the graph obtained from $\mathcal{G}$ by ``cutting'' $e$, 
namely by removing $e$ and let two flags attached to the end vertices 
of $e$. If $e$ is a self-loop then the resulting two flags are attached to the same vertex. (See an illustration in Figure \ref{fig:cute})
\end{definition}

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=3cm, height=0.1cm]{cute.pdf}
\caption{ {\small Cutting an edge. }}
\label{fig:cute}
\end{minipage}
\end{figure}

\begin{definition}[Graph and subgraph with flags]\label{subfla}

$\bullet$ A graph $\mathcal{G}$ with flags  is a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ with 
a set $\mathfrak{f}$ of flags defined by the disjoint union of $\mathfrak{f}^1$ the set 
of flags obtained only from the cut of all edges of $\mathcal{G}$ and a set
$\mathfrak{f}^0$  of ``additional'' flags together with a relation which 
associates  with each additional flag a unique vertex. 
We denote a graph with  set $\mathfrak{f}^0$ of additional flags  as
$\mathcal{G}(\mathcal{V},\mathcal{E}, \mathfrak{f}^0)$. (See Figure \ref{fig:grafla}.)

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=4cm, height=1.5cm]{grafla.pdf}
\caption{ {\small A graph with flags, its  set $\mathfrak{f}^0$ of additional flags 
in red and set $\mathfrak{f}^1$ in blue after cutting its edges and removing
$\mathfrak{f}^0$. }}
\label{fig:grafla}
\end{minipage}
\end{figure}

$\bullet$ A c-subgraph $A$ of $\mathcal{G}(\mathcal{V},\mathcal{E}, \mathfrak{f}^0)$ is defined as a graph $A(\mathcal{V}_A,\mathcal{E}_A,\mathfrak{f}^0_A)$ the vertex set of which
is a subset of $\mathcal{V}$, the edge set of which 
is a subset of $\mathcal{E}$ together with their end vertices.
Call $\mathcal{E}_A'$ the set of edges incident to the vertices of $A$
and not contained in $\mathcal{E}_A$.
The flag set of $A$  contains a subset of $\mathfrak{f}^0$
plus additional flags attached to the vertices 
of $A$ obtained by cutting all  edges in $\mathcal{E}_A'$.
In symbols, $\mathcal{E}_A \subseteq \mathcal{E}$ and
$\mathcal{V}_A \subseteq \mathcal{V}$, $\mathfrak{f}^0_A = \mathfrak{f}^{0;0}_A \cup \mathfrak{f}^{0;1}_A(\mathcal{E}_A)$
with $\mathfrak{f}^{0;0}_A \subseteq \mathfrak{f}^0$ and $\mathfrak{f}^{0;1}_A (\mathcal{E}_A)\subseteq \mathfrak{f}^1$, where $\mathfrak{f}^{0;1}_A (\mathcal{E}_A)$ is the set of flags  
obtained by cutting all edges in $\mathcal{E}_A'$ 
and incident to vertices of $A$. 
We write $A \subseteq \mathcal{G}$. 
 (See $A$ as illustrated in Figure \ref{fig:cgra}.)

$\bullet$ A spanning c-subgraph $A$ of $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ is defined as   a c-subgraph $A(\mathcal{V}_A,\mathcal{E}_A,\mathfrak{f}^0_A)$ of $\mathcal{G}$ with all vertices  and all additional flags of $\mathcal{G}$. Hence $\mathcal{E}_A\subseteq \mathcal{E}$ and $\mathcal{V}_A = \mathcal{V}$, $\mathfrak{f}^0_A = \mathfrak{f}^{0} \cup \mathfrak{f}^{0;1}_A(\mathcal{E}_A)$. 
We denote it $A \Subset \mathcal{G}$. 
 (See $\tilde A$ as an illustration in Figure \ref{fig:cgra}.) 
\end{definition}

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=6cm, height=1.5cm]{cgra.pdf}
\vspace{0.1cm}
\caption{ {\small A graph $\mathcal{G}$, a c-subgraph $A$ defined by the edge $e$ and the spanning c-subgraph $\tilde A$ associated with $e$. }}
\label{fig:cgra}
\end{minipage}
\put(-238,-10){$\mathcal{G}$}
\put(-265,17){$e$}
\put(-177,-10){$ A$}
\put(-190,17){$e$}
\put(-120,-10){$\tilde A$}
\put(-138,17){$e$}
\end{figure}

Remark that a spanning c-subgraph has always a 
greater number of additional flags than the 
initial graph which spans it.  Moreover, one can define the rank and nullity of any (spanning c-sub-) graph with flags as in the ordinary situation. 
\begin{definition}[Edge contraction of graphs with flags]
\label{contfla}
Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ be a graph with flags. 
We define the contraction of a non self-loop 
edge $e$ in $\mathcal{G}$, i.e. $\mathcal{G}/e$, by the graph obtained
from $\mathcal{G}$ by removing $e$ and identifying 
the two end vertices into a new vertex having all their additional flags
and remaining incident lines.  For a self-loop $e$, 
contraction $\mathcal{G}/e$ and deletion $\mathcal{G}-e$ coincide. 
\end{definition}

Noting that the above contraction does not 
change the number of additional flags of a graph, the following proposition is straightforward.
\begin{proposition}\label{cutflag}
Let $\mathcal{G}(\mathcal{V},\mathcal{E}, \mathfrak{f}^0)$ be a graph with flags 
and $e$ be an edge. Then
\begin{eqnarray}
\mathfrak{f}^0 (\mathcal{G} \vee e) = \mathfrak{f}^0 \cup \{e_1,e_2\}\,,
\qquad 
\mathfrak{f}^0(\mathcal{G}/e) = \mathfrak{f}^0 \,,
\end{eqnarray}
where the two flags $e_{1,2}$ are obtained from cutting $e$.
\end{proposition}

Operations for graphs in the sense of  Definition \ref{def:grop} 
can be reported for graphs with flags. The disjoint union graph  $\mathcal{G}_1 \sqcup \mathcal{G}_2$
and product graph $\mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2$ keep the same sense with set of additional flags the disjoint union of additional flag sets. 
Spanning c-subgraphs of $\mathcal{G}_1 \sqcup \mathcal{G}_2$ and
$\mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2$ are of the form 
$A_{1} \sqcup A_{2}$ and $A_{1}\cdot_{v_1,v_2}  A_{2}$, 
respectively, with $A_i \Subset \mathcal{G}_i$. The only point  to 
check is that, given $A_i (\mathcal{V}(\mathcal{G}_i), \mathcal{E}_{A_i}, \mathfrak{f}^{0}_{A_i}=\mathfrak{f}^{0}_{\mathcal{G}_i}\cup \mathfrak{f}^{0;1}(\mathcal{E}_{A_i}))$  
\begin{eqnarray}
&& \mathfrak{f}^0_{A_{1} \sqcup A_{2}} = \mathfrak{f}^0_{\mathcal{G}_1} \cup \mathfrak{f}^0_{\mathcal{G}_2}\,,
\qquad 
\mathfrak{f}^{0;1}_{A_{1} \sqcup A_{2}}(\mathcal{E}_{A_1} \cup \mathcal{E}_{A_2}) =
\mathfrak{f}^{0;1}_{A_1}(\mathcal{E}_{A_1}) \cup \mathfrak{f}^{0;1}_{A_2}(\mathcal{E}_{A_2})\, \label{foia}\\
&&\mathfrak{f}^0_{A_{1} \cdot_{v_1,v_2}  A_{2}} = \mathfrak{f}^0_{\mathcal{G}_1} \cup \mathfrak{f}^0_{\mathcal{G}_2}\,,
\qquad
\mathfrak{f}^{0;1}_{A_{1}\cdot_{v_1,v_2}  A_{2}}(\mathcal{E}_{A_1} \cup \mathcal{E}_{A_2}) =
\mathfrak{f}^{0;1}_{A_1}(\mathcal{E}_{A_1}) \cup \mathfrak{f}^{0;1}_{A_2}(\mathcal{E}_{A_2})\,. 
\label{foib}
\end{eqnarray}
This holds because the flags obtained by cutting $(\mathcal{E}_{A_1} \cup \mathcal{E}_{A_2})'$ in $\mathcal{G}_1 \sqcup \mathcal{G}_2$ or by cutting $(\mathcal{E}_{A_1} \cup \mathcal{E}_{A_2})'$ in $\mathcal{G}_1 \cdot_{v_1,v_2}  \mathcal{G}_2$
turns out to be identical to
the flags obtained from cutting $\mathcal{E}_{A_1}'$ in $\mathcal{G}_1$ (letting $\mathcal{G}_{2}$ untouched) with those from  cutting $\mathcal{E}_{A_2}'$ in $\mathcal{G}_2$
(letting $\mathcal{G}_{1}$ untouched).  One finally shows that spanning c-subgraphs
of $\mathcal{G}_1 \sqcup \mathcal{G}_2$ and of $\mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2$ are one-to-one.



We can now identify a new polynomial for graphs with 
flags and list its main properties. 

\begin{definition}[Tutte polynomial for graphs with flags] \label{def:tuflag}
Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ be a graph with flags. 
The Tutte polynomial of $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ is given by 
\begin{equation}
    \mathcal{T}_{\mathcal{G}}(x,y,t)=\sum_{A\Subset \mathcal{G}}(x-1)^{{\rm r}\,(\mathcal{G})-{\rm r}\,(A)}(y-1)^{n(A)} \,
t^{f(A)},
\label{tuflaexp}
\end{equation}
with $f(A) :=| \mathfrak{f}^0| + |\mathfrak{f}^{0;1}_A(\mathcal{E}_A)|$.
\end{definition}
The following proposition holds. 
\begin{proposition}[Operations on Tutte polynomial 2] 
\label{optufla}
Let $\mathcal{G}_1$ and $\mathcal{G}_2$ be two disjoint graphs with flags, then 
\begin{eqnarray} 
\mathcal{T}_{\mathcal{G}_1 \sqcup \mathcal{G}_2}= \mathcal{T}_{\mathcal{G}_1} \mathcal{T}_{\mathcal{G}_2} = \mathcal{T}_{\mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2}\,. 
\label{cups}
\end{eqnarray}
for any  vertices $v_{1,2}$ in $\mathcal{G}_{1,2}$, respectively. 
\end{proposition}
\proof  From Proposition \ref{optu},  
we must check only the behavior of the sets of flags
and prove that they factorize properly. 
Consider $\mathcal{G} = \mathcal{G}_1 \sqcup \mathcal{G}_2$ or $\mathcal{G} = \mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2$ their spanning c-subgraphs $A \Subset \mathcal{G}$ can be simply expressed as subsets  $A = A_1 \sqcup A_2 \subset  \mathcal{G}_1 \sqcup \mathcal{G}_2$ or 
$A_1 \cdot_{v_1,v_2} A_2 \subset \mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2$
where $A_{1,2} \Subset \mathcal{G}_{1,2}$. 
The proof is then immediate from the fact that 
 $\mathfrak{f}^0_{A_1 \sqcup A_2} = \mathfrak{f}^{0}_{A_1 \cdot_{v_1,v_2} A_2}
 = \mathfrak{f}^{0}_{A_1} \cup \mathfrak{f}^{0}_{A_2}$ such that
\begin{equation}
f(A_1 \sqcup A_2) = f(A_1) + f(A_2) = f(A_1 \cdot_{v_1,v_2} A_2 )\,.
\end{equation}
\qed

We are now in position to prove our first new result. 
\begin{theorem}[Contraction and cut on Tutte polynomial]
\label{theo:contutefla}
Let $e$ be a regular edge of $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$. The
Tutte polynomial of $\mathcal{G}$ satisfies the relations
\begin{eqnarray}
\mathcal{T}_{\mathcal{G}}&=& \mathcal{T}_{\mathcal{G} \vee e}  + \mathcal{T}_{\mathcal{G}/e} \,.
\label{regcont} \\
\mathcal{T}_{\mathcal{G}\vee e} &=& t^2\, \mathcal{T}_{\mathcal{G} -  e}  \,.
\label{gevee}
\end{eqnarray} 
For a bridge $e$, one has $\mathcal{T}_{\mathcal{G}/e} = \mathcal{T}_{\mathcal{G}-e}= t^{-2}\, \mathcal{T}_{\mathcal{G} \vee e} $, and 
\begin{equation}
\mathcal{T}_{\mathcal{G}} = (1+ (x-1)t^2)\mathcal{T}_{\mathcal{G}/ e} \,.
\label{bricont}
\end{equation}
For a self-loop $e$, one has $\mathcal{T}_{\mathcal{G}/e} = \mathcal{T}_{\mathcal{G}-e}= t^{-2}\, \mathcal{T}_{\mathcal{G} \vee e}$ and 
\begin{equation}
\mathcal{T}_{\mathcal{G}} = (y-1+ t^2) \mathcal{T}_{\mathcal{G}- e} \,.
\label{selcont}
\end{equation}

\end{theorem}
\proof The proofs of these statements are similar to the ordinary one
for graph without flags. However, a special care has to 
be paid on the flags. 

Take a regular edge $e$. 
$\mathcal{G} \vee e$ has a set of vertex $\tilde\mathcal{V} = \mathcal{V}$ and
the number of connected components
$k(\mathcal{G} \vee e) = k(\mathcal{G})$. Then, it is direct to get
${\rm r}\, (\mathcal{G} \vee e) = {\rm r}\, \mathcal{G} = {\rm r}\, (\mathcal{G}-e)$.
Meanwhile, contracting $e$ in $\mathcal{G}$  keeps the same 
meaning, hence
${\rm r}\, (\mathcal{G}/e) = (|\mathcal{V}|-1) - k(\mathcal{G}) = {\rm r}\, (\mathcal{G})-1$.
Furthermore, $f(\mathcal{G} \vee e) = f(\mathcal{G}) + 2$
and $f(\mathcal{G}/e) = f(\mathcal{G})$.


We first focus on \eqref{regcont} and
decompose the Tutte polynomial in the ordinary form as
a sum on subsets containing $e$ and a remainder
that we must compare with 
$\mathcal{T}_{\mathcal{G} /e}$ and $\mathcal{T}_{\mathcal{G} \vee e}$, respectively. 

Let us choose a bijection 
between the two sets $\{A\Subset \mathcal{G}; e \notin A\} $ and
$\{ A \Subset \mathcal{G}\vee e\}$. 
For a regular edge $e$, $A\Subset \mathcal{G}$, with $e\notin A$,
uniquely defines $A' \Subset \mathcal{G} \vee e$ such that $A' = A$
namely they both have the same vertices, edges and flags. 
It is also simple to check that $\{A \Subset \mathcal{G} \vee e\}$ and
$\{ A \Subset \mathcal{G}-e\}$ are in one-to-one correspondence by just
removing from any $A\Subset \mathcal{G} \vee e$ the two additional 
flags introduced by the cut of $e$ in $\mathcal{G} \vee e$ and get
a spanning subset of $\mathcal{G} -e$. The mapping is clearly
invertible hence bijective.

Given $e$, a regular edge, consider  $A \Subset \mathcal{G} \vee e$,
its unique corresponding element $A'$
in $\{B\Subset \mathcal{G};e\notin B\}$ and $A''$ its corresponding
element in $\{ B \Subset \mathcal{G}-e\}$. 
 The monomial in $\mathcal{T}_{\mathcal{G}\vee e}$ related to $A$ 
can be recast in the form
\begin{eqnarray}
(x-1)^{{\rm r}\,(\mathcal{G}\vee e ) - {\rm r}\,(A)} (y-1)^{n(A)} t^{f(A)} 
&=& (x-1)^{{\rm r}\,(\mathcal{G}) - {\rm r}\,(A')} (y-1)^{n(A')} t^{f(A')} \,,\crcr
&=& (x-1)^{{\rm r}\,(\mathcal{G}-e) - {\rm r}\,(A'')} (y-1)^{n(A'')} t^{f(A'')+2}  \crcr
&&
\end{eqnarray}
This achieves the proof that (a) $\mathcal{T}_{\mathcal{G}\vee e}$ and $\sum_{A \Subset \mathcal{G}; e\notin A} (\cdot)$ has the same number of terms and the 
same monomials and (b) $\mathcal{T}_{\mathcal{G}\vee e} = t^2\, \mathcal{T}_{\mathcal{G} -e}$.


Let us deal with the contraction now.  
We  prove that $\{A\Subset \mathcal{G}; e\in A\} $ 
is one-to-one with $\{A \Subset \mathcal{G}/e\}$ for a regular
edge $e$. 
Given a regular
edge $e$, $A\Subset \mathcal{G}$, with $e \in A$, uniquely defines
$A' \Subset \mathcal{G}/e$ defined by the contraction of $e$ in $A$
(in the sense of Definition \ref{contfla}). 

Given $e$ a regular edge, $A\Subset \mathcal{G}/e$ and its unique corresponding subset $A' \Subset \mathcal{G}$, $e \in A'$,
we can  write  each monomial of $\mathcal{T}_{\mathcal{G}/e}$ as 
\begin{eqnarray}
(x-1)^{{\rm r}\,(\mathcal{G}/e) - {\rm r}\,(A)} (y-1)^{n(A)} t^{f(A)} 
= (x-1)^{{\rm r}\,(\mathcal{G})-1 - ({\rm r}\,(A')-1)} (y-1)^{n(A')} t^{f(A')} 
\end{eqnarray}
which achieves the proof that $\mathcal{T}_{\mathcal{G}/e}$ and
$\sum_{A \Subset \mathcal{G}; e\in A} (\cdot)$ has the same 
number of terms and the same terms. 
The proof of \eqref{regcont} and \eqref{gevee} is then complete.

We now prove $\mathcal{T}_{\mathcal{G}-e} = \mathcal{T}_{\mathcal{G}/e}$ and \eqref{bricont}.
Given a bridge $e$, $\mathcal{G}/e = \mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2$ 
and $\mathcal{G}-e =  \mathcal{G}_1 \sqcup \mathcal{G}_2$ for 
the maximal\footnote{Maximal is understood in the sense that 
the subgraph contains all vertices, all edges and all additional flags
of one bridge side.} subgraphs $\mathcal{G}_i$ on each side of the bridge $e$
with end vertices $v_{1,2}$.
The fact that $\mathcal{T}_{\mathcal{G}-e} = \mathcal{T}_{\mathcal{G}/e}$ follows from 
Proposition \ref{optufla}.

Second, $\{A \Subset \mathcal{G}; e\notin A\}$ is one-to-one with
$\{A \Subset \mathcal{G}/e\}$ since 
$\{A \Subset \mathcal{G}; e\notin A\}$ is one-to-one with
$\{A \Subset \mathcal{G}_1 \sqcup \mathcal{G}_2\}$ (each $A\Subset \mathcal{G}$, $e\notin A$
is uniquely mapped on $A'\Subset  \mathcal{G}_1 \sqcup \mathcal{G}_2$ by removing
simply the flags issued from the cut of $e$ in $A$) and also 
$\{A \Subset \mathcal{G}/e\} =  \{A \Subset \mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2\}$.


Consider a bridge $e$ in $\mathcal{G}$ and decompose the Tutte polynomial 
of $\mathcal{G}$  as
\begin{eqnarray}
  \mathcal{T}_{\mathcal{G}}(x,y,t)&=&
  \sum_{A\Subset \mathcal{G}; e \notin A } (x-1)^{{\rm r}\,(\mathcal{G}) -{\rm r}\, (A) } (y-1)^{n(A)} 
t^{f(A)} +\mathcal{T}_{\mathcal{G}/e} (x,y,t)
\crcr
&=& \sum_{A\Subset \mathcal{G}/e} (x-1)^{{\rm r}\,(\mathcal{G}/e)+1 -{\rm r}\, (A) } (y-1)^{n(A)} 
t^{f(A)+2} +\mathcal{T}_{\mathcal{G}/e} (x,y,t) \crcr
&=& [1+(x-1)t^2] \;\mathcal{T}_{\mathcal{G}/e}(x,y,t)\,.
\end{eqnarray}
Furthermore, consider the bijection between $\{A \Subset \mathcal{G}\vee e\}$
and $\{A \Subset \mathcal{G} -e\}$ which maps any $A\Subset \mathcal{G}\vee e$
uniquely on $A' \Subset \mathcal{G} -e$ by removing two flags from the cut of $e$.
Then, the monomial in $\mathcal{T}_{\mathcal{G} \vee e}$
\begin{equation}
(x-1)^{{\rm r}\,(\mathcal{G}\vee e) - {\rm r}\,(A)}(y-1)^{n(A)} t^{f(A)}
= (x-1)^{{\rm r}\,(\mathcal{G}-e) - {\rm r}\,(A')}(y-1)^{n(A')} t^{f(A')+2}
\end{equation}
yielding $\mathcal{T}_{\mathcal{G}\vee e} = t^2\, \mathcal{T}_{\mathcal{G} -e}= t^2\,\mathcal{T}_{\mathcal{G}/e}$
which achieves the proof of \eqref{bricont}. 

Last, for a self-loop $e$, we prove \eqref{selcont}. For a self-loop $e$, $\mathcal{T}_{\mathcal{G}-e} = \mathcal{T}_{\mathcal{G} /e}$
holds by definition. Using the  bijection between 
$\{A \Subset \mathcal{G}; e\notin A\}$ and $\{A \Subset  \mathcal{G} - e \}$
mapping $A$ to $A'$ the same subgraph without the two additional
flags of $A$ from the cut of $e$, and 
the bijection between  $\{A \Subset \mathcal{G}; e \in A\}$ and $\{A \Subset  \mathcal{G} - e \}$ given by just deleting $e$ in $A\Subset \mathcal{G}$, we have 
\begin{eqnarray}
\mathcal{T}_{\mathcal{G}}(x,y,t)&=& 
  \sum_{A\Subset \mathcal{G}- e } (x-1)^{{\rm r}\,(\mathcal{G}-e) -{\rm r}\, (A') } (y-1)^{n(A')} 
t^{f(A')+2} \crcr
&+& \sum_{A\Subset \mathcal{G}- e } (x-1)^{{\rm r}\,(\mathcal{G}-e) -{\rm r}\, (A') } (y-1)^{n(A')+1} 
t^{f(A')}
\crcr
&=& [y-1+t^2] \;\mathcal{T}_{\mathcal{G}-e}(x,y,t)\,.
\end{eqnarray}
The last equality from \eqref{selcont} comes from the
bijection between $\{A\Subset \mathcal{G} \vee e\}$ and $\{A\Subset \mathcal{G} -e\}$
given by removing in $A$ the two flags coming from $e$ 
and note that in $\mathcal{T}_{\mathcal{G} \vee e}$ each monomial can be recast in the form
\begin{equation}
(x-1)^{{\rm r}\,(\mathcal{G}\vee e) -{\rm r}\, (A) } (y-1)^{n(A)} 
t^{f(A)} = (x-1)^{{\rm r}\,(\mathcal{G}-e) - {\rm r}\, (A')} (y-1)^{n(A')} 
t^{f(A') + 2}
\end{equation} 
so that, once again, $\mathcal{T}_{\mathcal{G} \vee e} = t^2 \, \mathcal{T}_{\mathcal{G} -e}$ 
which achieves the proof of \eqref{selcont}.

\qed

\vspace{0.4cm}

Few remarks concerning this definition of Tutte polynomial
for graphs with flags follow:

$\bullet$ For any edge $e$, we note that  $\mathcal{T}_{\mathcal{G} \vee e}  = t^2\,\mathcal{T}_{\mathcal{G} -e}$.
 

$\bullet$ The contraction/cut rule seems to be the natural one
in the formalism including the notion of flags. 

$\bullet$ The polynomial $\mathcal{T}_{\mathcal{G}}$ has always a factor of $t^{|\mathfrak{f}^{0}|}$
which should be removed by a new normalization. Note that the naive prescription to introduce the variable $t^{f(A)- f(\mathcal{G})}$ does not work. 
In order to remove this factor, we need another property of $\mathcal{T}$
which follows. 

$\bullet$ {\bf Universality}: We know that the universal form of the Tutte polynomial \eqref{tutexp} is given by the following
statement [Theorem 2, Chap. X \cite{bollo3}]:
{\it There is a unique map 
$U: \mathcal{G} \rightarrow \mathbb{Z}[x,y,\alpha,\sigma,\tau]$ such that for the graph $E_n$ made  uniquely with 
$n$ vertices 
\begin{equation}
U(E_n)=\alpha^n\,,
\end{equation}
for every $n\geq1$ and for every $e\in E(G)$, we have
\begin{eqnarray}
U(G)&=&\left\{\begin{array}{ll} xU(G- e) \mbox{ if $e$ is a bridge},\\
 yU(G- e) \mbox{ if $e$ is a loop},\\
 \sigma U(G- e)  + \tau U(G/e) \mbox{ if $e$ is neither a bridge nor a loop}. \end{array}
\right.
\label{univ}
\end{eqnarray}
Furthermore,
\begin{equation}
U(G)=\alpha^{k(G)}\sigma^{n(G)}\tau^{r(G)} T_{G}(\alpha x/\tau,y/\sigma)\,.
\label{foncoftutte}
\end{equation}
}
The Tutte polynomial for $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ satisfies
 the recurrence relation given by Theorem \ref{theo:contutefla}
which is remarkably of the form \eqref{univ}.
 Indeed, after a change of variables as
\begin{eqnarray}
\left\{\begin{array}{ll}X=(x-1)t^2+1\\
 Y=y-1+t^2. \end{array}
\right.
\end{eqnarray}
and given the fact that, for a given graph $\mathcal{G}(\mathcal{V},\mathcal{E})$
and $A \Subset \mathcal{G}$,  
\begin{equation}
f(A)=|\mathfrak{f}^0|+2(|\mathcal{E}|-|\mathcal{E}_A|)\,,
\end{equation}
we get 
\begin{equation}
 \mathcal{T}_{\mathcal{G}}(x,y,t)=t^{|\mathfrak{f}^0|}t^{2n(\mathcal{G})} \,T_{\mathcal{G}}(X, \frac{Y}{t^2}) \,.
\end{equation}
	If we set $\sigma=t^2$, $\alpha=\tau=1$ in \eqref{univ},  $\mathcal{T}_{\mathcal{G}}$ is merely one solution of 
\eqref{univ} modified by a factor $t^{|\mathfrak{f}^0|}$
and thus defines a $t$-deformed version of $T_{\mathcal{G}}$. 


$\bullet$ The exponent of $t$ in $\mathcal{T}_{\mathcal{G}}(x,y,t)/t^{|\mathfrak{f}^0|}$ is always even this is justified by the fact that each c-spanning subgraph 
is defined via successive cut of edges yielding each two flags. 
This can be easily removed by performing a change 
in the variable $t \to t^{1/2}$.

$\bullet$ The terminal form made with $m$ bridges, $n$ self-loops
and $q$ additional flags admits the Tutte polynomial 
\begin{equation}
 ( 1+ (x-1)t^2)^m\, (y-1 + t^2)^n \,t^q=X^m Y^n t^q\,,
\end{equation}
after some  change of variables. 

$\bullet$ Putting $t=1$ in $\mathcal{T}_{\mathcal{G}}(x,y,t)$ yields the ordinary 
Tutte polynomial 
\begin{equation}
\mathcal{T}_{\mathcal{G}}(x,y,1)=T_{\mathcal{G}}(x,y)
\end{equation}
obeying the ordinary  contraction/deletion rule. 

 
\vspace{0.4cm}

\section{Ribbon graphs and Bollobas-Riordan polynomial}
\label{sect:ribbonbollo}


In this section, we first recall the generalization
of the Tutte polynomial to ribbon graphs known as the BR 
polynomial for ribbon graphs \cite{bollo,bollo2}. 
Then, we investigate ribbon with flags according to our previous
developments of Subsection \ref{subsec:tufla}. 

\subsection{Ribbon graphs}
\label{subsect:ribbon}


We start by some basic facts on the ribbon graphs and
 their BR polynomial.

\begin{definition}[Ribbon graphs \cite{bollo}\cite{krf}]\label{def:ribbongraph}
	A ribbon graph $\mathcal{G}$ is  a (not necessarily orientable) surface with boundary represented as the union of two 
sets of closed topological discs called vertices $\mathcal{V}$ and edges $\mathcal{E}.$ These sets satisfy the following:

$\bullet$ Vertices and edges intersect by  disjoint line segment,

$\bullet$ each such line segment lies on the boundary of precisely one vertex and one edge,

$\bullet$ every edge contains exactly two such line segments.
\end{definition}

The previous notion of self-loops, bridges, regular edges, 
terminal forms (of Definition \ref{def:edg}) 
can be easily reported here when the ribbon graph
is seen as a simple graph namely when forgetting its ribbon 
character. Ribbon edges can be  twisted as well. 
Introducing twisted edges has some  consequences on the orientability 
of the ribbon graph.  
In addition, there is a new topological notion that we now
describe. 

\begin{definition}[Faces \cite{bollo}]
A face is a component of a boundary of $\mathcal{G}$ considered as a geometric ribbon graph, and hence as surface with boundary. 
\end{definition}
If $\mathcal{G}$ is regarded as the neighborhood of a graph embedded into a 
surface, $\mathcal{F}$ is the set of faces of the embedding. 
A ribbon graph is  denoted by $\mathcal{G}(\mathcal{V},\mathcal{E})$.


\begin{definition}[Deletion and contraction \cite{bollo}] 
\label{def:cdelrib}

Let $\mathcal{G}$ be a ribbon graph and $e$ one of its edges. 

$\bullet$ We call $\mathcal{G}-e$ the ribbon graph obtained from 
$\mathcal{G}$ by deleting $e$ and keeping the end vertices 
as closed discs. 

$\bullet$ If $e$ is not a self-loop, the graph $\mathcal{G}/e$  obtained by contracting $e$ is defined from $\mathcal{G}$ by deleting $e$ and 
identifying its end vertices $v_{1,2}$ into a new vertex which possesses
all edges in the same cyclic order as their appeared on $v_{1,2}$.

$\bullet$ If $e$ is a trivial twisted self-loop, 
contraction is deletion: $\mathcal{G}-e = \mathcal{G}/e$. 
The contraction of a trivial untwisted self-loop  $e$
is the deletion of the self-loop and the addition of a new 
connected component vertex $v_0$ to 
the graph  $\mathcal{G}-e$. We write $\mathcal{G}/e = (\mathcal{G}-e)\sqcup \{v_0\}$.


\end{definition}

 The notion of contraction of a twisted or untwisted self-loop $e$
in $\mathcal{G}$ is subtle since it coincides with the edge deletion in the graph $\mathcal{G}^*$ dual of $\mathcal{G}$, namely $(\mathcal{G}^*-e^*)^*$ \cite{bollo}.
The above point on the contraction of these self-loops 
is compatible with this dual notion of deletion. 
 

Spanning subgraphs in the present context 
keep the sense of Definition \ref{span}: $A \Subset \mathcal{G}$
if $A$ is defined by a subset of edges $\mathcal{E}_A \subseteq \mathcal{E}$ 
and possesses all vertices $\mathcal{V}$ of $\mathcal{G}$.

\begin{definition}[BR polynomial 1 \cite{bollo}]
\label{def:bol}
Let $\mathcal{G}$ be a ribbon graph. We define the ribbon graph polynomial of $\mathcal{G}$ to be
\begin{equation}
R_{\mathcal{G}}(x,y,z) =\sum_{A\Subset \mathcal{G}} (x-1)^{{\rm r}\,(\mathcal{G})-{\rm r}\,(A)}(y-1)^{n(A)}z^{k(A)-F(A)+n(A)},
\label{brpoly}
\end{equation}
where $F(A)$ is the number of faces of $A$.
\end{definition}
Notice that we use the same convention, with $(y-1)$
parametrizing the nullity of the subgraph, as  
in the Tutte polynomials defined so far. 
This is different from the convention of 
BR in \cite{bollo} which rather uses $y$. 
It is however simple to change 
variable at any moment and recover
the convention used therein. 

The BR polynomial obeys as well
a contraction and deletion rule. 

\begin{theorem}[Contraction and deletion \cite{bollo}]
Let $\mathcal{G}$ be a ribbon graph. If $e$ is a regular edge, then
\begin{equation}
R_{\mathcal{G}}=R_{\mathcal{G}/e}+ R_{\mathcal{G}-e}\,,
\end{equation} 
for every bridge $e$ of $\mathcal{G}$, one has
\begin{equation}
R_{\mathcal{G}}=x \, R_{\mathcal{G}/e}\,,
\label{cbrid}
\end{equation} 
for a trivial untwisted self-loop
\begin{equation}
R_{\mathcal{G}}=y \,R_{\mathcal{G}-e}\,,
\label{csel}
\end{equation}
and for a trivial twisted self-loop, the following holds
\begin{equation}
R_{\mathcal{G}}=(1+(y-1)z) \,R_{\mathcal{G}-e}\,.
\label{ctsel}
\end{equation}
\end{theorem}


We emphasize that the relations  \eqref{cbrid}-\eqref{ctsel} 
are useful for the determination of the BR polynomial from 
terminal forms which play the role of boundary conditions. 
The explicit formula (which has to be distinguished from 
the sum over spanning subgraphs) of BR polynomials of one-vertex 
ribbon graphs are not entirely known, to our
knowledge \cite{avo}. We will only restrict
to these trivial self-loops in the remaining analysis.  

The following fact turns out to be crucial. 
During contraction and deletion moves
of a regular edge, the exponent of $z$, namely 
${k(A) - F(A) + n(A)}$, in  the BR polynomial is invariant. Indeed, for a regular
edge $e$, $k(A)$ does not change whether or not $e\in A$;
$n(A)$, as a difference $|\mathcal{E}_A| - {\rm r}\,(A)$, is also invariant whether or not $e\in A$. Finally, $F(A)$ is never affected by the contraction if $e\in A$
whereas,  if $e \notin A$, $F(A)$ remains constant after deletion
of $e$ in the graph $\mathcal{G}$. One could have chosen different
types of exponent functions of these ingredients for defining a different
polynomial invariant under contraction and deletion. However, 
the above choice is motivated by the fact that the combination
\begin{equation}
k(A) - F(A) + n(A)= 2k(A) - (|\mathcal{V}| - |\mathcal{E}_A| - F(A))
\end{equation}
 is nothing
but the genus or twice the genus (for oriented surfaces) of
the subgraph  $A$.  Furthermore, writing the exponent in this form also helps for the determination of the terminal forms because $k(A) - F(A)$ 
and $n(A)$ turn out to be additive quantities with respect to 
the product of disjoint graphs. More motivations can be found in \cite{bollo}.
These remarks will be exploited in the following 
in order to uncover other types of BR polynomials. 



\subsection{Ribbon graphs with flags}
\label{subset:ribfla}

This section starts another main result of this work. 
We identify an extended form of the BR polynomial for ribbon graphs with 
flags. If such a polynomial must be related with the polynomial
by Krajewski et al. \cite{krf} introduced for the same type of
graphs that mapping will be only clear after finding the multivariate form 
of the polynomial found in the present work and then recasting the 
intertwined sums of spanning subgraphs related by Chmutov duality  
as used  in \cite{krf} in terms of a unique spanning c-subgraph sum.
These subtleties will be not treated of the present work since
they will not yield much insights for our final goal. 


\begin{definition}[Ribbon flags and external points]
\label{ribflag}
A ribbon flag or half-ribbon (or half-edge or simply flag, without ambiguity) is a ribbon incident to a unique vertex by a unique segment and without forming loops. A flag has two segments one touching a vertex 
and another free or external segment. The end-points of any free 
segment are called external points of the flag.  

\end{definition}
A ribbon flag is drawn in Figure \ref{fig:ribbonflag}.
\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=3cm, height=1.3cm]{ribbonfla.pdf}
\vspace{0.1cm}
\caption{ {\small A ribbon flag $f$ incident to one vertex disc. 
The two segments of $f$, $s_1$ touching the vertex 
and $s_2$ a free segment with its end points $a$ 
and $b$.}}
\label{fig:ribbonflag}
\end{minipage}
\put(-189,17){$s_1$}
\put(-119,17){$s_2$}
\put(-129,30){$a$}
\put(-129,0){$b$}
\end{figure}

It is clear that this definition is purely combinatorial. 
The notion of flag can be introduced as a topological 
ingredient of the ribbon graph as well. Such a flag
is nothing but a topological closed disc. It intersects
a vertex at one segment $s_1$ (see Figure \ref{fig:ribbonflag}). Consider on the boundary 
of the flag another segment $s_2$ disjoint from $s_1$. The segment
$s_2$ is the  external segment and it is introduced in order
to distinguish the two connected segments of the boundary
of the flag. 

\begin{definition}[Cut of a ribbon edge \cite{krf}]
Let $\mathcal{G}(\mathcal{V}, \mathcal{E})$ be a ribbon graph and let $e$ be an edge.
The cut graph $\mathcal{G} \vee e$, is the graph obtained by 
removing $e$ and let two flags attached at the end vertices
of $e$. If $e$ is a self-loop, the two flags are on the same 
vertex.   
\end{definition}

The definitions of a ribbon graph with flags $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$  and
of its spanning c-subgraphs follow  naturally from Definition \ref{subfla} and will be refrained at this point. 
We denote again the spanning c-subgraph inclusion as $A \Subset \mathcal{G}$.

Considered as a geometric surface, note that cutting an edge
on a graph modifies the boundary faces of this graph. 
One can say that the new boundary faces follow the contour of the flags.  
 But combinatorially, we  introduce a 
 discrepancy between this type of faces and the initial
ones (which come from boundary of well formed edges).
This will be useful in the following section 
dealing with the tensor situation. 

\begin{definition}[Closed, open faces, strands and pinching \cite{Gurau:2009tz}]
\label{pinch}
Consider $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ a ribbon graph with flags.

$\bullet$ A closed or internal face is a boundary face component of a ribbon graph (regarded as a geometric ribbon) which never passes through any free segment of additional flags.  The set of closed faces is denoted $\mathcal{F}_{{\rm int}}$. (See the closed face $f_{1}$ in 
Figure \ref{fig:ribbonfla})

$\bullet$ An open  or external face is a boundary face component 
leaving an external point of some flag rejoining another external point.  
 The set of open faces is denoted  $\mathcal{F}_{{\rm ext}}$. (Examples of open faces are provided in Figure \ref{fig:ribbonfla}.)

$\bullet$ The two boundaries lines of a ribbon edge or a flag
are called strands. Each strand may belong to a closed or open face. 

$\bullet$ The set of faces $\mathcal{F}$ of a graph having a set of flags is defined by 
$\mathcal{F}_{{\rm int}} \cup \mathcal{F}_{{\rm ext}}$.

$\bullet$ A graph is said to be open if $\mathcal{F}_{{\rm ext}}\neq \emptyset$
i.e. $\mathfrak{f}^0\neq \emptyset$. 
It is closed otherwise. 

$\bullet$ The pinching of a flag is a combinatorial procedure 
performed at one flag  which identifies its external points
and hence its strands.  


$\bullet$ The pinched graph $\widetilde{\mathcal{G}}(\widetilde{\mathcal{V}},\widetilde{\mathcal{E}},\widetilde{\mathfrak{f}}^0)$ of a ribbon graph $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ is a closed ribbon graph obtained after the pinching of all its flags. Thus $\widetilde{\mathcal{V}} = \mathcal{V}$, $\widetilde{\mathcal{E}}= \mathcal{E}$,
and  $|\widetilde{\mathfrak{f}}^0| = |\mathfrak{f}^0|$ 
where $\widetilde{\mathfrak{f}}^0$ are now pinched flags;  $\widetilde{\mathcal{F}}=\mathcal{F}_{{\rm int}}\cup \mathcal{F}'$ where $\mathcal{F}'$ are additional faces obtained from $\mathcal{F}_{{\rm ext}}$ after the pinching of $\mathcal{G}$.

\end{definition}

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=10cm, height=2.6cm]{pinch.pdf}
\vspace{0.1cm}
\caption{ {\small A ribbon graph $\mathcal{G}$ with a closed face $f_1$ 
(in red) and open faces $f_{2,3,4}$ (in black, green and blue, resp.).
The pinched graph $\widetilde{\mathcal{G}}$ and its two closed faces $f_1$ and $\tilde f$. }}
\label{fig:ribbonfla}
\end{minipage}
\put(-269,23){$f_1$}
\put(-199,17){$f_2$}
\put(-239,50){$f_3$}
\put(-269,-5){$f_4$}
\put(-310,-5){$\mathcal{G}$}
\put(-75,50){$\tilde f$}
\put(-103,23){$f_1$}
\put(-145,-5){$\widetilde{\mathcal{G}}$}
\end{figure}


Note that, for a graph without flags $\mathfrak{f}^0= \emptyset$, 
$\mathcal{G}$ is closed and $\widetilde{\mathcal{F}}=\mathcal{F}=\mathcal{F}_{{\rm int}}$ and $\widetilde{\mathcal{G}}=\mathcal{G}$.

\begin{definition}[Boundary graph \cite{Gurau:2009tz}]
\label{bnd}
$\bullet$ The boundary $\partial{\mathcal{G}}$ of a ribbon graph $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ 
is a simple graph $\partial{\mathcal{G}}({\mathcal{V}}_{\partial},{\mathcal{E}}_{\partial})$
in the sense of Definition \ref{def:graph}
such that ${\mathcal{V}}_{\partial}$ is one-to-one with $\mathfrak{f}^0$
and ${\mathcal{E}}_{\partial}$ is one-to-one with $\mathcal{F}_{{\rm ext}}$. 
(The boundary of the graph given in Figure \ref{fig:ribbonfla}
is provided in  Figure \ref{fig:boundary}.)

$\bullet$ The boundary of a closed graph is empty. 
\end{definition}

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=5cm, height=2.6cm]{boundary.pdf}
\vspace{0.1cm}
\caption{ {\small The boundary $\partial{\mathcal{G}}$ of $\mathcal{G}$ of Figure \ref{fig:ribbonfla} is represented in dashed lines.}}
\label{fig:boundary}
\end{minipage}
\end{figure}


As a result, $\partial \widetilde{\mathcal{G}} = \emptyset$ since the pinched
graph $\widetilde{\mathcal{G}}$ is closed.
In practice, the boundary graph $\partial{\mathcal{G}}$ can be read off the
graph $\mathcal{G}$ by inserting a vertex with degree
two at each flag. External faces which are the edges of $\partial{\mathcal{G}}$ 
are incident to these vertices. 
Hence, a boundary graph  realizes combinatorially what is expected
from the total pinching  of a ribbon graph. 
Since $\partial{\mathcal{G}}$ has only vertices with always two incident lines
or one incident line if the two sides of the flag defined in fact the
same external face, then it is not difficult to prove the following
statement.  

\begin{proposition}\label{pinbor}
Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ be a ribbon graph with flags, 
 $\widetilde{\mathcal{G}}(\widetilde{\mathcal{V}},\widetilde{\mathcal{E}},\widetilde{\mathfrak{f}}^0)$ its pinching and $\partial{\mathcal{G}}({\mathcal{V}}_{\partial},{\mathcal{E}}_{\partial})$
its boundary. One has
\begin{equation}
\mathcal{F}' = {\mathcal{C}}_{\partial}\,,
\end{equation}
where $\mathcal{F}'$ are the additional closed faces obtained
by the pinching of $\mathcal{G}$ and ${\mathcal{C}}_{\partial}$ are the connected 
components of the boundary graph $\partial{\mathcal{G}}$.
\end{proposition}
The notion of edge contraction and deletion for graphs with flags 
can be simply understood as in Definition \ref{def:cdelrib}
without mentioning flags. 


\begin{definition}[BR polynomial for ribbon graphs with flags]
Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ be a ribbon graph with flags.  
We define the ribbon graph polynomial of $\mathcal{G}$ to be
\begin{equation}
\mathcal{R}_{\mathcal{G}}(x,y,z,s,t)
=\sum_{A\Subset \mathcal{G}} (x-1)^{{\rm r}\,(\mathcal{G})-{\rm r}\,(A)}(y-1)^{n(A)}
z^{k(A)-F_{{\rm int}}(A)+n(A)} \, s^{C_\partial(A)} \, t^{f(A)},
\label{brfla}
\end{equation}
where $C_\partial(A)= |{\mathcal{C}}_{\partial}(A)|$ is the number 
of connected component of the boundary of $A$
and $F_{{\rm int}}(A)= |\mathcal{F}_{{\rm int}}(A)|$.
\end{definition}

The polynomial $\mathcal{R}$ \eqref{brfla} generalizes the BR polynomial 
$R$ \eqref{brpoly}. The latter $R$
 can be only recovered from $\mathcal{R}$ for closed ribbon graphs and
at the limit $t=1$. 
After performing the change of variable $s\to z^{-1}$,
we are led to another extension of the BR polynomial 
for ribbon graphs with flags. 
We will refer the second polynomial to as $\mathcal{R}'$. 
In symbol, for a graph $\mathcal{G}$, we write
\begin{equation}
\mathcal{R}_{\mathcal{G}}(x,y,z,z^{-1},t) = \mathcal{R}'_{\mathcal{G}}(x,y,z,t) \,,\qquad
\mathcal{R}'_{\mathcal{G}}(x,y,z,t=1) = R_{\widetilde{\mathcal{G}}}(x,y,z)\,,
\end{equation}
where $R_{(\cdot)}$ is given by Definition \ref{def:bol}. 


Graph operations ($\mathcal{G}_1 \sqcup \mathcal{G}_2$ and $\mathcal{G}_1 \cdot_{v_1,v_2} 
\mathcal{G}_2$) extend to ribbon graphs \cite{bollo} and 
ribbon graphs with flags. The product $\mathcal{G}_1 \cdot_{v_1,v_2} 
\mathcal{G}_2$ at the vertex resulting from merging $v_1$ and 
$v_2$ (in the sense of Definition \ref{def:cdelrib}) 
respects the cyclic order of all edges and flags on the previous vertices $v_1$ and $v_2$. The fact that $R_{\mathcal{G}_1 \sqcup \mathcal{G}_2}
= R_{\mathcal{G}_1} R_{\mathcal{G}_2} = R_{\mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2}$ holds
for ribbon graphs without flags \cite{bollo} can be 
extended  for ribbon graphs with flags under particular conditions. The following proposition holds.
\begin{proposition}[Operations on BR polynomials] 
\label{opBRfla}
Let $\mathcal{G}_1$ and $\mathcal{G}_2$ be two disjoint ribbon graphs with flags, then 
\begin{eqnarray} 
\mathcal{R}_{\mathcal{G}_1 \sqcup \mathcal{G}_2}&=& \mathcal{R}_{\mathcal{G}_1}
 \mathcal{R}_{\mathcal{G}_2}\,,
\label{brcups1}\\
\mathcal{R}'_{\mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2} 
&=&\mathcal{R}'_{\mathcal{G}_1} \mathcal{R}'_{\mathcal{G}_2} \,,
\label{brcups2}
\end{eqnarray}
for any disjoint vertices $v_{1,2}$ in $\mathcal{G}_{1,2}$, respectively. 
\end{proposition}
\proof  Using Propositions \ref{optu} and \ref{optufla},
one must only check the behavior of the exponents 
$k(A)-F_{{\rm int}}(A)+n(A)$ and $C_\partial(A)$, for any $A\Subset \mathcal{G}$.  

Consider first $\mathcal{G} = \mathcal{G}_1 \sqcup \mathcal{G}_2$.  A spanning c-subgraph $A \Subset \mathcal{G}$ expresses as $A = A_1 \sqcup A_2 \Subset  \mathcal{G}_1 \sqcup \mathcal{G}_2$ 
with $A_{1,2} \Subset \mathcal{G}_{1,2}$. It is straightforward to see that 
$k(A)$, $F_{{\rm int}}(A)$, $n(A)$ and $C_\partial(A)$ are
all additive quantities and therefore 
\eqref{brcups1} is recovered.  

Consider now $\mathcal{G} = \mathcal{G}_1 \cdot_{v_1,v_2} \mathcal{G}_2$
and $A =A_1 \cdot_{v_1,v_2} A_2 \Subset \mathcal{G}$. 
We have the following relations
\begin{equation}
k(A) = k(A_1) + k(A_2) -1 \,,\qquad
n(A) = n(A_1) + n(A_2)\,,
\label{kna}
\end{equation}
where the last equality follows from $|\mathcal{V}(A)| = |\mathcal{V}(A_1)| + |\mathcal{V}(A_2)| - 1$.
More  issues arise for the faces. 
Taking product at two vertices $v_1$ of $A_1$ and $v_2$  of $A_2$, 
one face $f_1$ of $A_1$ and one face $f_2$ of $A_2$ enter in contact and merge. Three different situations may occur: 

- Both $f_i\in \mathcal{F}_{{\rm int}}(A_i)$, $i=1,2$, then 
\begin{eqnarray}
F_{{\rm int}}(A) = F_{{\rm int}}(A_1) + F_{{\rm int}}(A_2) -1 \,,
\qquad 
C_\partial(A) = C_\partial(A_1) + C_\partial(A_2)\,.
\label{fint}
\end{eqnarray}

- $f_1\in \mathcal{F}_{{\rm int}}(A_1)$ and $f_2 \in \mathcal{F}_{{\rm ext}}(A_2)$
(or vice-versa), then \eqref{fint} still holds 
because the internal face $f_1$ is lost (becoming external by touching 
$f_2$) whereas the connected component
of the boundary graph $\partial A_2$ which contains $f_2$ 
is conserved. 

- Both $f_i\in \mathcal{F}_{{\rm ext}}(A_i)$, then 
\begin{eqnarray}
F_{{\rm int}}(A) = F_{{\rm int}}(A_1) + F_{{\rm int}}(A_2) \,,
\qquad 
C_\partial(A) = C_\partial(A_1) + C_\partial(A_2)-1\,.
\label{ext}
\end{eqnarray}
It is clear that, by changing $s\to z^{-1}$, the two quantities
$F_{{\rm int}}(A)$ and $C_{\partial}(A)$ 
add up as exponent of the $z$ variable  and always
cancel the contribution from the $k(A)$, see \eqref{kna}.
 
\qed



We come to the properties of  $\mathcal{R}_{\mathcal{G}}$. 

\begin{theorem}[Contraction and cut on BR polynomial]
\label{theo:BRext}
Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ be a ribbon graph with flags. Then,
for a regular edge $e$, 
\begin{equation}
\mathcal{R}_{\mathcal{G}}=\mathcal{R}_{ \mathcal{G}\vee e} +\mathcal{R}_{\mathcal{G}/e}\,,
\label{retcondel}
\end{equation} 
for a bridge $e$, we have 
\begin{equation}
\mathcal{R}_{\mathcal{G}} =(x-1)\mathcal{R}_{\mathcal{G} \vee e}+ \mathcal{R}_{\mathcal{G}/e}\,;
\label{retbri}
\end{equation} 
 for a trivial twisted self-loop $e$, the following holds 
\begin{equation}
\mathcal{R}_{\mathcal{G}}=\mathcal{R}_{\mathcal{G} \vee e} + (y-1)z \,\mathcal{R}_{\mathcal{G}/e}\,,
\label{retsel2}
\end{equation} 
whereas for a trivial untwisted self-loop $e$, we have
\begin{equation}
\mathcal{R}_{\mathcal{G}}=\mathcal{R}_{\mathcal{G} \vee e} + (y-1) \mathcal{R}_{\mathcal{G}/e}\,.
\label{retsel1}
\end{equation} 
\end{theorem}
\proof  In the following proof, 
spanning c-subgraphs are simply called subgraphs. 
Let us make two preliminary remarks. 
(A) The subgraphs $A$ of $\mathcal{G}$ which do not contain $e$ are precisely the subgraphs of $\mathcal{G}\vee e$. 
(B) Also, if $e$ is not a self-loop then the map $A\mapsto A/e$ provides a bijection from the subgraphs of $\mathcal{G}$ which contain $e$ to the subgraphs of $\mathcal{G}/e$. 
Note importantly that $A$ and $A/e$ does not have
the same vertices and edges but have the  same
flags and so same faces. 

Let us prove \eqref{retcondel}. For a regular edge $e$,
let $A \Subset \mathcal{G}\vee e$,  $A'$ its partner in $\mathcal{G}$ such that 
 $e \notin A'$ by remark (A). 
The fact that the monomial of $A$ in $\mathcal{R}_{\mathcal{G}\vee e}$
and the monomial corresponding  to $A'$ 
in $\mathcal{R}_{\mathcal{G}}$ are identical is simple to check.  Then
$\sum_{A\Subset \mathcal{G}; e \notin A }(\cdot)  = \mathcal{R}_{\mathcal{G}\vee e}$.

We concentrate now on the remaining  sum related to the contraction
of $e$. In  particular, we focus on sets of faces during the contraction.  
Choose $A\Subset \mathcal{G}$ with $e \in A$ and, by remark (B), let 
 $A' \Subset \mathcal{G}/e$ be its corresponding subgraph.
One has
\begin{eqnarray}
F_{{\rm int}}(A)=F_{{\rm int}}(A') \,\,\mbox{ and } \,\,
C_\partial(A)=C_\partial(A')  \,.
\end{eqnarray}
The monomial of $\mathcal{R}_{\mathcal{G}/e}$ related to $A$ is of the form 
\begin{eqnarray}
&&
(x-1)^{{\rm r}\,(\mathcal{G}/e) - {\rm r}\,(A)} (y-1)^{n(A)}z^{k(A)-F_{{\rm int}}(A)+n(A)} \, s^{C_\partial(A)} \, t^{f(A)} \crcr
&&= (x-1)^{{\rm r}\,(\mathcal{G})-1 - ({\rm r}\,(A')-1)} (y-1)^{n(A')}
 z^{k(A')-F_{{\rm int}}(A')+n(A')} \, s^{C_\partial(A')} \, t^{f(A')} 
\end{eqnarray}
which achieves the proof that $\mathcal{R}_{\mathcal{G}/e}=\sum_{A \Subset \mathcal{G}; e\in A} (\cdot)$ and then \eqref{retcondel} is obtained.


We prove now \eqref{retbri}. 
Let $e$ be a bridge in $\mathcal{G}$ and decompose $\mathcal{R}_{\mathcal{G}}$ as
$\sum_{A\Subset \mathcal{G}; e \notin A }(\cdot)  + \mathcal{R}_{\mathcal{G}/e}$. 
It remains to prove that the first sum can be mapped 
on $(x-1)\mathcal{R}_{\mathcal{G} \vee e}$ 
but this is straightforward from 
${\rm r}\,(\mathcal{G}) = {\rm r}\,(\mathcal{G}\vee e)+1$ and since all other terms remain
unchanged. 

The proofs of relations \eqref{retsel2} and \eqref{retsel1} are now provided. 
Consider a trivial (twisted or not) self-loop  $e$ in $\mathcal{G}$, 
then  $\sum_{A\Subset \mathcal{G}; e \notin A }(\cdot) =\mathcal{R}_{\mathcal{G} \vee e}$
still  holds in any case. Moreover, 
 if $e$ is a self-loop, 
the subgraphs of $\mathcal{G}-e$ are one-to-one with the subgraphs of $\mathcal{G}$ containing $e.$ The passage from the subgraphs of $\mathcal{G}$ containing $e$ to those of $\mathcal{G}-e$ or conversely is just by deleting $e$ or gluing $e$ to the corresponding subgraph. 

Consider  a trivial twisted self-loop  $e$ in $\mathcal{G}$. The contraction 
of $e$ coincides with its deletion.  Hence to each $A\Subset \mathcal{G}$ with $e \in A$ 
and its corresponding $A' \Subset \mathcal{G}/e= \mathcal{G}-e$ 
(obtained by just deleting $e$ in $A$), 
one finds that $F_{{\rm int}}(A) = F_{{\rm int}}(A')$ 
and $C_\partial(A) = C_\partial(A')$. Therefore,
one has the relation between  the terms:
\begin{eqnarray}
&&
(x-1)^{{\rm r}\,(\mathcal{G}) -{\rm r}\, (A) } (y-1)^{n(A)} 
 z^{k(A)-F_{{\rm int}}(A)+n(A)} \, s^{C_\partial(A)} \, t^{f(A)}  
\crcr
&&= (x-1)^{{\rm r}\,(\mathcal{G}- e) -{\rm r}\, (A') } (y-1)^{n(A')+1} 
 z^{k(A')-F_{{\rm int}}(A')+n(A')+1} \, s^{C_\partial(A')} \, t^{f(A')}\,.
\end{eqnarray}
Thus \eqref{retsel2} is satisfied. 

Because $e$ is a trivial untwisted self-loop, the contraction of $e$
is  its deletion  supplemented by an addition of
a new vertex on $\mathcal{G}-e$ that we denote $\mathcal{G}/e = (\mathcal{G} -e)\cup \{v_0\}$. 
Given $A\Subset \mathcal{G}$ with $e \in A$, 
we associate a unique corresponding element $A'$ in $(\mathcal{G} -e)\cup \{v_0\}$ such that we delete $e$ in $A$ and add to it $v_0$ 
as a new vertex. We can infer that $F_{{\rm int}}(A) = F_{{\rm int}}(A')$, 
and $C_\partial(A) = C_\partial(A')$. 
Thus, the following relation between the terms corresponding
to $A$ and $A'$ holds: 
\begin{eqnarray}
&&
(x-1)^{{\rm r}\,(\mathcal{G}) -{\rm r}\, (A) } (y-1)^{n(A)} 
 z^{k(A)-F_{{\rm int}}(A)+n(A)} \, s^{C_\partial(A)} \, t^{f(A)}  
\crcr
&&  (x-1)^{{\rm r}\,(\mathcal{G}/e) -{\rm r}\, (A') } (y-1)^{n(A')+1} 
 z^{(k(A')-1) - F_{{\rm int}}(A')+(n(A')+1)} \, s^{C_\partial(A')} \, t^{f(A')} \,,
\end{eqnarray}
so that \eqref{retsel1} is obtained.  

\qed

Importantly,  we cannot map
$\mathcal{R}_{\mathcal{G} \vee e}$ and $\mathcal{R}_{\mathcal{G}/e}$ for a bridge 
or a trivial self-loop $e$. Such a mapping can be recovered
only after a reduction.  

\begin{corollary}
Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ be a ribbon graph with flags. Then,
for a regular edge $e$, 
\begin{equation}
\mathcal{R}'_{\mathcal{G}}=\mathcal{R}'_{ \mathcal{G}\vee e} +\mathcal{R}'_{\mathcal{G}/e}\,,
\qquad 
\mathcal{R}'_{\mathcal{G} \vee e} = t^2 \mathcal{R}'_{\mathcal{G} -e}\,;
\label{retcondelp}
\end{equation} 
for a bridge $e$, we have 
$\mathcal{R}'_{\mathcal{G}/e} = \mathcal{R}'_{\mathcal{G}-e} = t^{-2} \, \mathcal{R}'_{\mathcal{G} \vee e}$
\begin{equation}
\mathcal{R}'_{\mathcal{G}} =[(x-1)t^2 +1]  \mathcal{R}'_{\mathcal{G}/e}\,;
\label{retbrip}
\end{equation} 
for a trivial twisted self-loop, $\mathcal{R}'_{\mathcal{G}/e}=\mathcal{R}'_{\mathcal{G}-e}=t^{-2}\mathcal{R}'_{\mathcal{G} \vee e}$ and 
\begin{equation}
\mathcal{R}_{\mathcal{G}}=[t^2 + (y-1)z] \,\mathcal{R}_{\mathcal{G}/e}\,,
\label{retselp2}
\end{equation} 
whereas for a trivial untwisted self-loop, we have
$\mathcal{R}'_{\mathcal{G}/e}=\mathcal{R}'_{\mathcal{G}-e}=t^{-2}\mathcal{R}'_{\mathcal{G} \vee e}$
and 
\begin{equation}
\mathcal{R}_{\mathcal{G}}=[t^2+ (y-1)] \mathcal{R}_{\mathcal{G}/e}\,.
\label{retselp1}
\end{equation} 
\end{corollary}
\proof This is a consequence of 
Theorem \ref{theo:BRext}, Proposition \ref{opBRfla} and Theorem \ref{theo:contutefla} and the fact that $\mathcal{R}'_{\mathcal{G} \vee e} = t^2 \mathcal{R}'_{\mathcal{G} -e}$ that we need to detail. 

The first equation of \eqref{retcondelp} 
needs no comment after Theorem \ref{theo:contutefla}. Let us prove the second 
equation of \eqref{retcondelp}. There is a one-to-one assignment between 
spanning c-subgraphs $A \Subset \mathcal{G} \vee e$ and $A' \Subset \mathcal{G} -e$
given by the following: $A'$ is obtained from $A$ by removing the
two flags issued from the cut of $e$. Note  immediately that $\mathcal{F}_{{\rm int}}(A)
\subset \mathcal{F}_{{\rm int}}(A')$.  We have
$\mathcal{F}_{{\rm int}}(A) \cup {\mathcal{C}}_{\partial}(A)= \mathcal{F}(\tilde A)$, 
where $\tilde A$ is the pinched graph obtained from $A$.
But the pinched graph $\tilde A$ coincides with 
the pinched graph $\tilde A '$ with, however, two additional flags. 
Indeed, they have the same vertices, edges, $\mathfrak{f}^0(\tilde A)=
\mathfrak{f}^0(\tilde A')\cup \{f_{e,1},f_{e,2}\}$, where $f_{e,i}$, $i=1,2$,
are obtained from cutting $e$, and for any face in $\tilde A$, one
has a unique corresponding face in $\tilde A'$. This is because, 
given a face of $\tilde A$,  either this face comes from $\mathcal{F}_{{\rm int}}(A)$
and then should be in $\mathcal{F}_{{\rm int}}(A')$, or this face comes from ${\mathcal{C}}_{\partial}(A)$ and therefore two cases may occur: (i) the removal of the 
flags $f_{e;i}$ in $A$ yields directly a closed face of $A'$ and this  before pinching $A'$, such that this faces belongs to $\mathcal{F}_{{\rm int}}(A')$; 
(ii) the removal of the flags $f_{e;i}$ in $A$ yields still an open
face in $A'$ and, so, the face belongs to ${\mathcal{C}}_{\partial}(A')$. 
The unicity of the face correspondence follows immediately by 
reversing the reasoning. Hence, $F(\tilde A)= F(\tilde A')$ and
$f(A) = f(A')+2$, such that using Theorem \ref{theo:contutefla} for
the remaining part, one can map the terms of $\mathcal{R}'_{\mathcal{G} \vee e}$ to those of $t^2\mathcal{R}'_{\mathcal{G} -e}$.

One notices that $\mathcal{R}'_{\mathcal{G} \vee e}=t^2\mathcal{R}'_{\mathcal{G} -e}$
is true for any edge and not only for regular ones. 
For special edges, $\mathcal{R}'_{\mathcal{G}}$ can be computed using Proposition \ref{opBRfla} along the lines of Theorem \ref{theo:contutefla}
and Theorem \ref{theo:BRext}.
Equations in \eqref{retselp2} and \eqref{retselp1} 
simply follows from \eqref{retsel2} and \eqref{retsel1} of Theorem 
\ref{theo:BRext}, respectively, and simple operations on flags as performed in Theorem \ref{theo:contutefla}.

\qed 

We summarize the main features of the BR polynomial 
for ribbon graphs with flags:


$\bullet$ In the ribbon formulation, once again, 
the cut and contraction are natural. 

$\bullet$ $\mathcal{R}$, $\mathcal{R}'$ and $\mathcal{T}$ have similar properties concerning the number of flags $|\mathfrak{f}^0|$ and the even exponent of the $t$ variable. 


$\bullet$ {\bf Universality}: Only the polynomial $\mathcal{R}'$ 
is guaranteed to have a universal property. This follows 
from the ordinary arguments for the universal property 
of the BR polynomials for closed graphs with weighted in the recurrence
relation, for ordinary edges
\begin{eqnarray}
\phi(\mathcal{G}) = \sigma \phi(\mathcal{G}-e) + \tau \phi(\mathcal{G}/e) \,,
\end{eqnarray}
 with initial conditions, for any bridge $e$ $\phi(\mathcal{G}) = X \phi(\mathcal{G}/e)$
and the data of all BR polynomials for one-vertex ribbon graphs \cite{bollo}. Given \eqref{retcondelp}, once again by performing some change of variables, we can recast the relations satisfied by $\mathcal{R}'$ in this form. 

$\bullet$ The polynomial $\mathcal{R}'$ evaluated on terminal 
forms made with $p$ bridges, $m$  trivial untwisted self-loops, $n$ 
 twisted self-loops and $q$ flags is easily computable as
\begin{equation}
[(x-1)t^2 + 1]^p\,[t^2 + y-1]^m\, [t^2 + (y-1)z]^n\, t^q
= X^p Y^m Z^n t^q\,.
\end{equation}



$\bullet$ Note that, although there is a one-to-one map between
$\{A \Subset \mathcal{G} \vee e\}$ and $\{A' \Subset \mathcal{G} -e\}$
(see in the proof above), $A'$ has the same vertices and edges but different
flags and so different faces. There is {\it a priori} no relation 
between $\mathcal{R}_{\mathcal{G} \vee e}$ and  $\mathcal{R}_{\mathcal{G} -e}$ due to 
the discrepancy between their number of internal faces
and boundary components. A relation between 
the polynomial of $\mathcal{G} \vee e$ and $\mathcal{G} -e$ can be
only recovered for the $\mathcal{R}'$ polynomial. 
For any edge $e$, $\mathcal{R}'_{\mathcal{G} \vee e} = t^2 \mathcal{R}'_{\mathcal{G} -e}$. 

$\bullet$ We have 
\begin{equation}
\mathcal{R}_{\mathcal{G}}(x,y,z,z^{-1},t) = \mathcal{R}'_{\mathcal{G}}(x,y,z,t) \,,
\qquad 
\mathcal{R}'_{\mathcal{G}} (x,y,z,t=1) =R_{\mathcal{G}}(x,y,z)\,,   
\end{equation}
hence $\mathcal{R}_{\mathcal{G}}$ and $\mathcal{R}'_{\mathcal{G}}$ are generalized 
BR polynomials satisfying contraction and deletion 
operations. Finally, to recover the Tutte polynomial
we set
\begin{equation}
\mathcal{R}_{\mathcal{G}}(x,y,z=1,s=1,t) = \mathcal{T}_{\mathcal{G}}(x,y,t) \,. 
\end{equation}
from which the ordinary Tutte polynomial $T_{\mathcal{G}}$
is directly inferred. 

\vspace{0.4cm}

\section{Rank $D$ stranded graphs with flags and a generalized polynomial invariant}
\label{sect:tgraph}


This section undertakes the definition of a new polynomial
for particular graphs which aims at generalizing the BR polynomial $\mathcal{R}$ for graphs on surfaces
with boundaries in its most expanded form 
as treated in the Section \ref{subset:ribfla}. 
The central notion of graphs discussed below is
combinatorial and can be always pictured in a 3D space. 
Our main result appears in Theorem \ref{theo:contens}
after a thorough definition of the type of graphs 
extending ribbon graphs with flags for which a generalized polynomial invariant turns out to exist. 

The primary notion of rank $D$ colored tensor graphs considered here has been introduced by Gurau in \cite{Gurau:2009tw}. As ribbon graphs can be dually mapped onto triangulations of surfaces in 2D, colored tensor graphs can be interpreted as simplicial complexes
or dual of triangulations of  topological spaces in any dimension. 
They are of particular interest in certain quantum field theoretical frameworks defined with tensor fields hence the name 
tensor graphs\footnote{Ribbon graphs are, in this
sense, rank 2 or matrix graphs.}.
The importance of these graphs has been highlighted 
by Gurau which proved that the cellular structure
associated with these colored graphs generates dually
only simplicial pseudo-manifolds of $D$ dimensions
\cite{Gurau:2010nd}.  It has been also proved 
that a colored tensor graph which is bipartite 
induces naturally an orientation of the 
dual complex \cite{Caravelli:2010nh}. 

Some anterior studies have addressed the 
extension of the BR polynomial for higher dimensional 
object within the framework of such graphs. Mainly, two authors Gurau \cite{Gurau:2009tz} and Tanasa \cite{Tanasa:2010me} 
have defined two separate notions of extended BR polynomial. 
Let us do a blitz review of their results and compare 
these to the one obtained in the present work.  

Gurau defined a multivariate polynomial invariant for colored tensor  graphs dually associated with simplicial complexes with boundaries for any dimension $D$. The polynomial that we obtain in the present work admits a multivariate form which is related to the polynomial obtained by this author restricted to 3D but extends it to a larger type of graph than only the colored tensor graphs. We emphasize 
that the difficulties encountered by Gurau (as well as Tanasa, see below) 
for defining a contraction procedure for such type of graphs
without destroying the entire graph structure  
will be improved our scheme.  

In a different perspective, the work by Tanasa in \cite{Tanasa:2010me} 
deals with tensor graphs without colors which are equipped with
 another  vertex. The polynomial as worked out by this author is only valid
for graphs triangulating topological objects without boundary. The polynomial that we define is radically different from that one in several features, since mainly, it relies on the presence of colors in the graph. 


\subsection{Stranded, tensor, colored graphs with flags}
\label{subset:tgraphs}

 After some operations, the initial type of rank $D$ colored tensor graphs generates a final class of graphs which will be the one of interest in our analysis.  Like ribbon graphs, colored tensor graphs have both a topological meaning (realized in the dual triangulation) and a combinatorial formulation that will be  our main concern here.  
Before defining colored tensor graphs, let us introduce the  
combinatorial concept of stranded graph structure, the true backbone
of this theory.

\vspace{0.4cm}

\noindent{\bf Stranded and tensor graphs.} 
We start by primary notions of stranded structures 
and graphs. 

\begin{definition}[Stranded vertex and edge]\label{def:svert}
$\bullet$ A rank $D$ stranded vertex is a collection of segments called
 bows or strands which can be drawn in a 3-ball hemisphere (or  
a spherical cup in a three dimensional space) such that:

\begin{enumerate}
\item[(a)] the bows are not intersecting;
\item[(b)] all end points of the bows are drawn on 
the boundary (circle) of the equatorial disc (or section) called the vertex
frontier; 
\item[(c)] these end points can be partitioned
in sets called pre-flags with $0,1,2,\dots, D$ elements;
\item[(d)] the pre-flags should  form a connected collection
that is each pre-flag should be connected to any other 
pre-flag by a tree of bows. 
\end{enumerate} 
The coordination (or valence or degree) of a rank $D$ stranded vertex
is the number of its pre-flags. 
By convention, (C1) we include a particular vertex made with one
 disc and assume that it is a stranded vertex of any rank made 
 with a unique closed strand and (C2) a point is a rank 0 stranded vertex. 

\noindent $\bullet$ A rank $D$ stranded edge is a collection of segments called again strands such that:

\begin{enumerate}
\item[(a')] the strands are not intersecting (but
can cross, i.e. can be non parallel);
\item[(b')] the end points of the strands can be 
partitioned in two disjoint parts called sets of end segments of the
edge such that a strand cannot have its end points 
in the same set of end segments;  

\item[(c')] the number of strands is $D$.
\end{enumerate} 
\end{definition}

Rank $D >0$ stranded vertices just enforce that any entering strand in
the vertex should be exiting by another point at the frontier
of the vertex. According to our convention, the ordinary disc
and ribbon edges of ribbon graphs are valid stranded vertex 
and stranded edges. 
  
The notion of connectivity should be clarified. Vertices (with 
connected pre-flags) and edges are by convention connected objects 
even though graphically they sometimes appear disconnected
in the ordinary topological sense. This is will be justified
later on based on the dual that can represent 
such objects after few more constraints.  
Examples of stranded vertices and edges with rank $D=4$ 
and $D=5$, respectively, have been provided in Figure \ref{fig:vxedge}.


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=11cm, height=3cm]{vxedge.pdf}
\vspace{0.1cm}
\caption{ {\small A rank 4 stranded vertex $v$ of coordination 6, with
connected pre-flags (highlighted with different colors) with crossing bows; 
a trivial disc vertex $d$; a rank 5 edge $e$ with non parallel strands.}}
\label{fig:vxedge}
\end{minipage}
\put(-250,-10){$v$}
\put(-130,5){$d$}
\put(-50,5){$e$}
\end{figure}




\begin{definition}[Stranded and tensor graphs]\label{def:tens}
$\bullet$ A rank $D$ stranded graph $\mathcal{G}$ is a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$
which admits:
\begin{enumerate} 

\item[(i)] rank $D$ stranded vertices;

\item[(ii)] rank at most $D$ stranded edges;

\item[(iii)] One vertex and one edge intersect 
by one set of end segments of the edge which should coincide with a pre-flag at the frontier vertex.  
All intersections of vertices and edges are pairwise distinct. 

\end{enumerate} 


$\bullet$ A rank $D$ tensor graph $\mathcal{G}$ is a rank $D$ stranded graph such that: 

\begin{enumerate}  

\item[(i')] the vertices of $\mathcal{G}$ have a fixed coordination $D+1$ 
and their  pre-flags have a fixed cardinal $D$. From the point of 
view of the pre-flags, the pattern followed by each stranded vertex is that of the complete graph $K_{D+1}$;

\item[(ii')] the edges of $\mathcal{G}$ are of rank $D$ 
and their strands are parallel.


\end{enumerate} 

\end{definition}

Some illustrations of a rank 3 stranded and tensor graphs are given in Figure \ref{fig:strangra} and \ref{fig:tensgra}, respectively.  

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=11cm, height=3cm]{strangra.pdf}
\caption{ {\small A rank 3 stranded graph.}}
\label{fig:strangra}
\end{minipage}
\end{figure}

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=11cm, height=3cm]{tensgra.pdf}
\caption{ {\small A rank 3 tensor graph with rank 3 vertices as  with 
fixed coordination 4, pre-flags with 3 points linked by bows according
to the pattern of $K_4$; edges are rank 3 with parallel strands.}}
\label{fig:tensgra}
\end{minipage}
\end{figure}

\vspace{0.4cm} 


It should be pointed out that,  although the vertices and 
edges of stranded and tensor graphs are drawn in 
a three dimensional space, we do not treat these as embedded
graphs. The reason for this follows. There is an equivalent
way to construct rank $D$ stranded vertices, edges and graphs
using uniquely combinatorial (permutation) maps \cite{tutte} (see Chap. X). For this we need to label each pre-flag point (or cross in the jargon
of \cite{krf}) and define to which it is associated. There should
be $\sigma_0$ a vertex map, $\sigma_1$ an edge map
and $\theta$ a pre-flag map partitioning the set of crosses. For simple and ribbon 
graphs such permutation triple exists \cite{tutte}. For instance,
they have been extensively used in \cite{krf} in order 
to extend Chmutov duality to ribbon graphs with flags. 
At this moment, there is no equivalent formulation for higher rank
stranded  graphs in the way we introduce it here. However, 
one realizes that these maps can be defined point by point
for each graph constituent. In other words, 
$\sigma_0$ should be defined
for each vertex, $\theta$ for each pre-flag, $\sigma_1$ for each 
edge. Remark that to capture the general features that these maps should satisfy for stranded or even tensor graphs can be a non trivial task.

 At the end, we will always consider as identical two rank $D$ stranded 
graphs which are defined by the same $(\sigma_0,\theta,\sigma_1)$.
Examples of identical vertices and edges have be given in Figures \ref{fig:samevert} and \ref{fig:embed}.
Thus we can modify a stranded graph and still obtain 
the same graph after moving the pre-flags at the frontier vertex
(the order of their points can be also changed),
deform and cross arbitrarily bows and strands. The sole
point to be required is to keep the incidence relations of strand segments
 between the labeled points.  For these reasons, henceforth, we will always use a ``minimal'' graphical representation for stranded vertices and edges which is the one defined by strands using the ``shortest'' path between the pre-flags points. 

A side remark is that, in Definition \ref{def:tens}, the
precision in (ii') that the strands of edges in tensor graphs 
are parallel seems now superfluous since, using the above combinatorial maps, we can always make parallel non parallel strands. 
The price to pay for satisfying that is to get  a more peculiar vertex with more bow crossings following the fact that we should
preserve the same incidence of bows. Hence, the word parallel  
in (ii') is seen as the simplest choice possible for edges
making as simple as possible the vertex in the case of tensor graphs. 

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{1\textwidth}
      \centering
\includegraphics[angle=0, width=9.5cm, height=3cm]{samevert.pdf}
\vspace{0.1cm}
\caption{ {\small Two identical vertices, $v_1$ and $v_2$, defined up to a rotation 
of their frontier; note that the pairing of pre-flag
points (labeled by colors here) is the same (deformation and crossing of their bows
are meaningless). $v_2$
will be not preferred though because one of its bows, the one 
between the two green pre-flag points, do not use the shortest
path between pre-flags points.}}
\label{fig:samevert}
\end{minipage}
\put(-295,-10){$v_1$}
\put(-132,-10){$v_2$}
\end{figure}


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=3cm, height=1.5cm]{nonemb.pdf}
\vspace{0.1cm}
\caption{ {\small Two identical rank 3 edges between two graphs
(shaded).}}
\label{fig:embed}
\end{minipage}
\put(-209,7){$\mathcal{G}_1$}
\put(-142,7){$\mathcal{G}_2$}
\put(-209,32){$\mathcal{G}_1$}
\put(-142,32){$\mathcal{G}_2$}
\end{figure}


Given a stranded graph and collapsing its stranded vertices to 
points and its edges to simple lines,  
 one obtains a simple graph in the sense of Definition  \ref{def:graph}. 
This justifies the fact that stranded graphs 
are graphs. Moreover, it is with respect to this 
simple graph point of view that we will say that a stranded graph 
is connected or not. In other words, a stranded graph 
is connected if its corresponding collapsed graph is connected.
For instance, both graphs of Figure \ref{fig:strangra}
and \ref{fig:tensgra} are connected. 

We denote, when no confusion is possible, 
$\mathcal{G}(\mathcal{V},\mathcal{E})$ a rank
$D$ stranded graph with vertex set $\mathcal{V}$ and edge 
set  $\mathcal{E}$. It can be seen that any rank $D$ stranded graph 
is a rank $D' $ stranded graph, with $D' \geq D$. This is however
not true for tensor graphs. Calling 
a rank $D$ stranded graph in the remaining 
will often refer to the minimal rank for which
this graph is well defined. 


\noindent{\bf Lower rank stranded graphs.} 
Let us give  low rank examples of the above
graphs which turns out to be either trivial or known. 

\begin{enumerate}
\item[(0)]  Rank 0 stranded graphs are simple graphs 
made with only points as vertices and no edges. 

\item[(1)] Rank 1 stranded graphs as for vertices 
segments (note that any pre-flag reduces to a point and, in order to
form a connected collection, one has to consider a unique
segment between two pre-flags) and for edges segments as well. 
Such rank 1 stranded graphs cannot be 
directly identified with simple graphs in the sense
of Definition \ref{def:graph}. They can be viewed as
simple graphs if one collapses all vertices to points.  
Hence, neither rank 0 nor rank 1 stranded graphs
allows to define  simple graphs in general. In fact, 
for any rank $D$, the simple graph structure 
cannot be directly achieved without  using
the collapsing procedure described above. 

 

\item[(2)]
General ribbon graphs, in the sense
of Definition \ref{def:ribbongraph}, are one-to-one 
with particular rank 2 stranded graphs. 
 Given a ribbon graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ (Definition \ref{def:ribbongraph})
and an edge $e$ of $\mathcal{G}$. The ribbon edge  $e$ touches 
its end vertex or vertices in two segments $s$ and $s'$.  
Consider the  two distinct segments on the boundary 
of $e$ which are not $s$ and $s'$ (denoted by $s_1$ and $s_2$
in Figure \ref{fig:derib}A).  
These two segments define the two (not intersecting and potentially
twisted) strands of a rank 2 stranded edge with 
$s$ and $s'$ as end segments. 
By convention, a vertex with no incident line is a stranded vertex. 
So it is a stranded graph of any rank  in particular $D= 2$.
Consider now a vertex $v$ of $\mathcal{G}$  with incident edges 
$e_1$, $e_2$, \dots, $e_p$, $p \in \mathbb{N}$.
We can construct a stranded vertex $v'$ of rank $2$ 
in the following manner. The frontier vertex of $v'$
is simply the boundary of $v$. 
The end points of end segments of $e_k$, $1\leq k \leq p$,
define the pre-flags (with exactly 2 points) of $v'$. 
From these pre-flags, one defines the bows of $v'$ 
as the segments  between the end segments 
of $e_k$ which lies in $v$. See Figure \ref{fig:derib}B.  


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=6cm, height=2cm]{dedcrib.pdf}
\caption{ {\small Ribbon edge and vertex of a ribbon graph as a rank 2 stranded edge and vertex of a stranded graph.}}
\label{fig:derib}
\end{minipage}
\put(-223,17){$s_1$}
\put(-223,35){$s_2$}
\put(-270,25){A}
\put(-70,25){B}
\end{figure}


Ribbon graphs equipped 
with vertices with fixed coordination equals to 3 are 
rank 2 tensor graphs. The reason why the converse is not
true is that, in any rank 2 tensor graph, the bows might be not cyclically disposed on the vertex frontier. Thus the definition of any ribbon graph vertex as a disc may be not always satisfied.  




\end{enumerate}

While a stranded graph can be regarded as an abstract object, 
 tensor graphs actually possess a topological content. 

\begin{definition}[Dual of a tensor graph]
\label{def:dualtens}
Let $\mathcal{G}$ be a rank $D$ tensor graph. 
A vertex of $\mathcal{G}$ represents a $D$ simplex 
and an edge of $\mathcal{G}$ represents a
$(D-1)$ simplex. 
The graph $\mathcal{G}$ is dual to a simplicial complex obtained from 
the gluing of $D$ simplexes along 
$(D-1)$ simplexes lying at their boundary.    
\end{definition}

As an illustration of the above definition, 
a rank 3 tensor graph represents a simplicial 
complex in 3D composed by tetrahedra (3-simplexes) which are glued along their boundary triangles (2-simplexes). For rank $D$ tensor graph, 
a pre-flag is of cardinal $D$. Each couple of points 
induces a segment in the pre-flag,  we obtain 
$D(D-1)/2$ disjoint segments. 
These pre-flag segments are graphically pictured 
by $D$ points or $D-1$ joined (adjacent) segments between 
these $D$ points at the frontier
vertex. One may interpret that these $D(D-1)/2$ disjoint 
segments as the number of $(D-2)$-simplexes of the boundary 
of a $D-1$ simplex. For $D=3$, there are $D(D-1)/2 = 3$  edges in a triangle. Combinatorially, we draw these edges
as $D=3$ points or $D-1 = 2$ joined segments.

We now come back to our previous convention that
stranded vertices and edges are connected. Because the
dual of these two entities are connected topological 
simplexes only under tensor graph axioms, we simply assume
that, in tensor graphs and by extension in 
stranded graphs, these objects are also connected.   

\begin{definition}[Rank $D$ flag]\label{def:tensflag}
A rank $D$ stranded flag (or half-edge or simply flags, when no confusion may occur)  is a collection of 
$D$ parallel segments called strands satisfying the same properties of strands of 
rank $D$ edges but the flag is incident to a unique rank $D' $ stranded vertex, with $D' \geq D$, by one of its set of end segments without forming a loop. 

A rank $D$ flag has two sets of end segments: one touching a vertex
and another called free or external set of end segments,
the elements of which called themselves free or external segments. 
The $D$ end-points of all free segments are called external points 
of the rank $D$ flag. (See Figure \ref{fig:tensflag}.)
\end{definition}



\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=1.5cm, height=2cm]{tensflag.pdf}
\caption{ {\small A rank 3 stranded flag with its external points $a$,
$b$ and $c$.}}
\label{fig:tensflag}
\end{minipage}
\put(-153,38){$a$}
\put(-145,25){$b$}
\put(-153,13){$c$}
\end{figure}

\begin{definition}[Cut of an edge]\label{def:cutedtens}
Let $\mathcal{G}(\mathcal{V},\mathcal{E})$ be a rank D stranded graph
and $e$ a rank $d$ edge of $\mathcal{G}$, $1\leq d \leq D$.
The cut graph $\mathcal{G} \vee e$ or the graph obtained from $\mathcal{G}$ by 
cutting $e$ is obtained by replacing the edge $e$ by two rank $d$ flags 
at the end vertices of $e$ and respecting the strand structure
of $e$.  (See Figure \ref{fig:cuttens}.) If $e$ is a self-loop, the two flags are on the same vertex.  
\end{definition}



\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=5cm, height=1cm]{cutens.pdf}
\caption{ {\small Cutting a rank 3 stranded edge.}}
\label{fig:cuttens}
\end{minipage}
\end{figure}


The cut graph $\mathcal{G} \vee e$ is called
a rank $D$ stranded  graph with flags.
The presence of flags is compatible
 with rank $D$ stranded vertices and edges.   
Furthermore, in 
a stranded graph, we will always consider that all pre-flags are used. 
In other words, all pre-flags are necessarily either in contact  with edges
 or in contact with flags.
An example of such a graph is provided in Figure \ref{fig:graphwfla}.

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=8cm, height=3cm]{graphwfla.pdf}
\caption{ {\small A rank 3 stranded graph with all pre-flags used.}}
\label{fig:graphwfla}
\end{minipage}
\end{figure}



Hence, given a set of additional flags $\mathfrak{f}^0$ in some stranded graph, 
assuming that $\mathfrak{f}^0=\emptyset$ simply 
means that all pre-flags are in contact with 
edges. 
Any rank $D$ stranded graph with additional set of flag $\mathfrak{f}^0$
is denoted $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$. 

The notion of c-subgraph and spanning c-subgraph 
follows naturally from Definition \ref{subfla} with 
however the new meaning of the cut operation. The spanning
c-subgraph inclusion will be again denoted by $A \Subset \mathcal{G}$. 
To keep track of the internal structure of the vertices, c-subgraphs will be preferred to subgraphs which adds to the fact that we will only use stranded graphs with all pre-flags fully connected to flags. 
This also justifies why in the formulation of  
\cite{Gurau:2009tz} the deletion an edge is in fact the cut
of the edge in the sense precisely defined above. Thus, 
the cut operation should be the natural operation
within this framework. 

Particular edges as self-loops, bridges
(defined through a cut of an edge  which brings 
an additional connected component in the graph), regular edges and terminal forms are extended in the present context because the stranded graph admits a graph structure. 

Most of the concepts of Definition \ref{pinch} are
valid for stranded graphs. 
Faces of a stranded graph $\mathcal{G}$ are the maximal connected components made with strands of $\mathcal{G}$. Closed faces never pass through any free segment of additional flags.  $\mathcal{F}_{{\rm int}}$ denotes the set of these closed faces. Open or external faces are maximally connected component leaving an external point of some flag rejoining another external point. The set of open faces is denoted  $\mathcal{F}_{{\rm ext}}$.
 As usual, the set of faces $\mathcal{F}$ of a graph  is defined by 
$\mathcal{F}_{{\rm int}} \cup \mathcal{F}_{{\rm ext}}$. Open and closed  stranded graphs
follows the same ideas as in Definition \ref{pinch} as well.

Several notions (such as open and closed face) which are totally combinatorial in the stranded situation bear a true topological
content in the tensor graph case. For instance, a closed face in a
rank 3 tensor graph is a 2D surface in the bulk (interior) of the dual triangulation. An open face is a surface intersecting the boundary of the simplicial  complex dual to the graph. 

Let us discuss in more details the structure of an edge $e$. 
Assuming that $e$ is of rank $d$, consider the two pre-flags $f_1$ and $f_2$  where $e$ is branched to its end vertex $v$ 
(a self-loop situation) or vertices $v_{1,2}$ (a non self-loop 
case). It may happen that, after branching $e$, $p$ closed faces 
are formed\footnote{If $e$ is a self-loop, $p \leq d$; if $e$ is not a self-loop,
$p\leq d/2$ if $d$ is even or $p \leq (d-1)/2$, if $d$ is odd.}
such that these closed faces are completely contained
in $e$ and $v$ or $v_{1,2}$.  These closed faces will be called {\bf inner
faces } of the edge. An edge with $p$ inner faces is called 
{\bf $p$--inner edge}. 
See Figure \ref{fig:neigh} A,B and C for an illustration 
in the rank 3 situation. 
The remaining strands passing through $f_1$ and $f_2$ which are not
used in the inner faces are called {\bf outer strands}. They connect $f_1$ and $f_2$
to other pre-flag families  $\{f_{1;i}\}$ and $\{f_{2;j}\}$,
called  {\bf neighbors} of $f_1$ and $f_2$ respectively 
(this has been also illustrated in  Figure \ref{fig:neigh}). 
Dealing with a self-loop, we add the condition 
that neighbor families should satisfy $f_1\notin \{f_{2;j}\}$ and $f_2\notin \{f_{1;i}\}$. Note that these two families may have pre-flags in common
for a self-loop situation. 
If one of the neighbor families is empty, it means that 
for a non self-loop case, $f_1$ or $f_2$ define a vertex. 
For the self-loop case, the families can be empty 
but then there should exist some bows between $f_1$ and $f_2$
and, if both families are empty, 
 $f_1$ and $f_2$ define together a vertex. 





For any type of edge, 

- Assuming that $\{f_{1;i}\}$ and $\{f_{2;j}\}$ 
are not empty, this implies that the outer strands 
of $f_1$ and $f_2$ are related by strands via $e$. Consequently,
$\{f_{1;i}\}$ and $\{f_{2;j}\}$ are connected
via strands in $e$. 

- Assuming that $\{f_{1;i}\}$
is empty  but $\{f_{2;j}\}\neq \emptyset$ (or vice-versa without loss of generality)  the outer strands of $f_2$  are all 
related via $e$ (and in the case of a self-loop, 
these outer strands may be related with bows
in common between $f_1$ and $f_2$). 
Therefore $\{f_{2;j}\}$ is connected
via strands in $e$. 

- Assuming that both $\{f_{1;i}\}$ and $\{f_{2;j}\}$
are empty, then $e$ generates only inner faces. 

The notion of edge contraction can 
be defined at this point. 



\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=12cm, height=4cm]{neigh.pdf}
\vspace{0.1cm}
\caption{ {\small Some rank 3 $p$--inner edges: 0--inner $e_1$ (A), 1--inner 
$e_2$ (B) and 2--inner $e_3$ (C) edges (with inner faces highlighted in red).
Outer strands highlighted (in green and blue) for each $p$--inner edge 
case of A, B, C and their attached neighbor pre-flags.}}
\label{fig:neigh}
\end{minipage}
\put(-280,-10){A}
\put(-298,75){$f_1$}
\put(-320,87){$f_{1;1}$}
\put(-350,35){$f_{1;2}$}
\put(-330,5){$f_{1;3}$}
\put(-265,60){$f_2$}
\put(-240,105){$f_{2;1}$}
\put(-280,78){$e_1$}
\put(-120,-10){B}
\put(-140,73){$f_1$}
\put(-163,82){$f_{1;1}$}
\put(-105,55){$f_2$}
\put(-83,103){$f_{2;1}$}
\put(-120,75){$e_2$}
\put(-10,-10){C}
\put(-30,53){$f_1$}
\put(-16,22){$f_{1;1}$}
\put(3,53){$f_2$}
\put(-15,87){$e_3$}
\put(-338,-10){$(v_1)$}
\put(-240,40){$(v_2)$}
\put(-170,-10){$(v_1)$}
\put(-80,40){$(v_2)$}
\put(15,30){$(v)$}
\end{figure}


\begin{definition}[Stranded edge contractions]\label{def:constran}
Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ a rank $D$ stranded graph 
with flags. Let $e$ be a rank $d$ edge with 
pre-flags $f_1$ and $f_2$ and consider their neighbor
families $\{f_{1;i}\}$ and $\{f_{2;j}\}$.  

$\bullet$ If $e$ is a rank $d$ $p$--inner edge but not a self-loop, the graph $\mathcal{G}/e$ obtained by contracting $e$ `softly' is defined from $\mathcal{G}$ by
removing the $p$ inner faces generated by $e$, 
 replacing $e$ and its end vertices $v_{1,2}$ by 
$p$  disjoint disc vertices and a new vertex $v'$ which possesses all edges
but $e$ and all flags in the same cyclic order as their appear on $v_{1}$ and $v_{2}$, and strands obtained by connecting directly $\{f_{1;i}\}$ and/or $\{f_{2;j}\}$ via the outer strands of $f_1$ and $f_2$.
 (See examples of rank 3 edge contraction in Figure \ref{fig:constra} 
A' and B'.)


$\bullet$ If $e$ is a rank $d$ $p$--inner self-loop,
the graph $\mathcal{G}/e$ obtained by contracting $e$ `softly'  is defined from $\mathcal{G}$ 
by  removing the $p$ inner faces of $e$, 
by replacing $e$ and its end vertex $v$ by $p$ disjoint disc vertices 
and one vertex $v'$ having all edges as $v$ but $e$ and all flags
and strands built in the similar way as previously 
done by connecting the neighbor families of $f_1$
and/or $f_2$. (See an example of rank 3 self-loop
 contraction in Figure \ref{fig:constra}C'.)

If there is no outer strand left after removing the $p$ inner faces
of $e$ then the vertex $v'$ is empty. 

$\bullet$ For any type of $p$--inner edges, 
the graph $(\mathcal{G}/e)^\natural$ obtained by  contracting $e$ `hardly' 
is defined in the same way as above for each type of edge but without adding the extra $p$-discs.  

\end{definition}


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=12cm, height=3cm]{constra.pdf}
\vspace{0.1cm}
\caption{ {\small Graphs A',B' and C' obtained after edge contraction of A, B and C of Figure \ref{fig:neigh}, respectively.}}
\label{fig:constra}
\end{minipage}
\put(-310,-10){A'}
\put(-150,-10){B'}
\put(-20,-10){C'}
\end{figure}


Soft and hard contractions agree obviously on $0$--inner edges. The result of a hard contraction can be always
inferred from that one of a soft contraction performed on the same 
graph by simply removing the extra discs introduced at the end of the
soft procedure.  Introducing this discrepancy in the edge contraction will be justified in the following.

The terms ``cyclic order'' can be removed from the definition
provided we keep track of the pairing of the pre-flags points.
The cyclic order preservation is a simple and convenient choice
for recovering the final vertex after the contraction.

One may directly check that contracting a non self-loop in a ribbon graph
can be immediately seen as a rank 2 edge (soft or hard) contraction. 
For self-loop in ribbon graphs, we conjecture that the soft contraction procedure agrees with ordinary contraction of ribbon self-loop once again.  In fact, one may check that a trivial self-loop contraction for a ribbon graph coincides with the notion contraction of a $p$--inner self-loop contraction in the soft sense of Definition \ref{def:constran},  with $p=0,1,2$, when the ribbon graph is viewed as a rank 2  stranded
 graph\footnote{
Indeed, for a ribbon graph, a trivial untwisted self loop
is equivalent to a 1-- or 2--inner self-loop. It is a 1--inner self-loop
if one of the face of the self-loop does not immediately
close in the vertex and pass through another edge. 
A trivial untwisted self-loop with one vertex and one edge is a 2--inner self-loop.  A trivial twisted self-loop can be 1-- or 0--inner self-loop, 
depending on the number of edges of the vertex having the
self-loop. 
If there is more than one edge in the vertex, it is a 0--inner
self-loop, otherwise it is a 1--inner self-loop. 
Treating systematically these configurations of trivial self-loops
in a ribbon graph,  one can prove the above claim for these cases. }.
For a general self-loop $e$, we have strong hints that the soft contraction still coincides with the simple contraction of $e$ in a ribbon graph $\mathcal{G}$ 
defined through the dual graph $(\mathcal{G}^* -e^*)^*=\mathcal{G}/e$ \cite{bollo} 
hence, our above conjecture. 
 

\begin{proposition}
Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ a rank $D$ stranded graph 
with flags. Let $e$ be a rank $d$ edge. 
The graphs $\mathcal{G}/e$ and $(\mathcal{G}/e)^{\natural}$ obtained by soft or hard contraction of $e$, respectively, admit a rank $D$ stranded structure. 
\end{proposition}
\proof 
The following does not depend on the type of contraction.   
After contraction of an edge $e$, remark that the remaining
edges in the graph $\mathcal{G}$ are untouched. Hence they 
are at most rank $D$ stranded edges. The gluing 
of these edges and vertices of the $\mathcal{G}/e$ 
is unchanged as well. 
Ignoring the potentially present $p$ discs which are rank $D$ stranded 
graphs for any $D$, the unique issue that we need to check is 
whether or not the vertex $v'$ obtained after edge contraction admits a rank $D$ stranded structure.

To proceed with  this, observe first that 
bows in $v'$ are defined to be previous non intersecting bows 
or merged bows from neighbors pre-flags.  
Obviously all these bows are not intersecting before and after contraction. 
The frontier vertex can be easily extended (by deformation) to 
contain all pre-flags of the vertex $v_1$
and $v_2$ except $f_1$ and $f_2$ the pre-flags 
of $e$. 
The key point is that the vertex $v'$ may be disconnected with 
respect to its pre-flags. One must check that 
every connected component in $v'$ are rank $D$ stranded vertices. 

The remaining point is then quickly solved from the fact that
before and after contraction all points are connected
via bows in the graph. 
This means that, before contraction, all pre-flags have all of their
points connected by bows to other pre-flag points. After contraction,
some of the bows are removed. 
But whenever a bow is removed its end points are removed as well. Thus all remaining bows (if exist) linking all pre-flags are either untouched or carefully reconnected
between themselves in the neighbor families of $f_1$ 
and/or $f_2$ (if exist). Hence there is no point
in any remaining pre-flags without bow attached. 
Now if the vertex $v'$ gets
disconnected and some of the pre-flags form a separate 
set, all points of these pre-flags must be fully connected
between themselves by bows. This ensures that any 
connected set of pre-flags forms a new stranded vertex 
with rank at most $D$. 

\qed

After the above discussion, the following proposition is  straightforward. 

\begin{proposition}[Rank evolution under contraction]\label{prop:rank}
Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ a rank $D$ stranded graph 
with flags. Let $e$ be a rank $d$ edge. 
The ranks of the graphs $\mathcal{G}/e$ and  $(\mathcal{G}/e)^\natural$ are less than or equal to $D$.  
\end{proposition}
 
 At this point, one may wonder if the additional discs obtained after soft edge contraction are not inessential features of the graphs
for the remaining analysis. In fact, they will be very useful for the preservation of number of faces  during the edge contraction of the
graph as it is the case for ribbon graphs.  Furthermore as discussed above, if one wants to match
with the definition of a deletion in the dual, they could become
totally relevant. Hard contractions are also useful but in another
context, for instance, contracting particular tensor subgraphs called dipoles (see for instance \cite{BenGeloun:2011rc}). We will 
however focus only soft contractions. 
What we shall need is just to 
partially remove the disc which could be generated 
and  work ``up to trivial discs''
hence in the framework of equivalence class of graphs.  


\begin{definition}[Graph equivalence class]
Let $D_{\mathcal{G}}$ be the subgraph in a rank $D$ stranded 
graph $\mathcal{G}$ defined by all of its trivial disc vertices
and $\mathcal{G} \setminus D_{\mathcal{G}}$ the rank $D$ stranded graph 
obtained after removing $D_{\mathcal{G}}$ from $\mathcal{G}$. 

Two rank $D$ stranded graphs $\mathcal{G}_1$ 
and $\mathcal{G}_2$ are ``equivalent up to trivial discs''  if and only if 
$\mathcal{G}_1\setminus D_{\mathcal{G}_1} = \mathcal{G}_2\setminus D_{\mathcal{G}_2}$. 
We note   $\mathcal{G}_1 \sim \mathcal{G}_2$. 
\end{definition}
One can check that $\sim$ is indeed an equivalence relation. 
The next important notion to identify is that of (spanning) c-subgraphs of an equivalence class $\mathfrak{G}$ of a graph $\mathcal{G}$. This can be done as follows. A (spanning) c-subgraph  $\mathfrak{g}$ of $\mathfrak{G}$ is the equivalence
class of a (spanning) c-subgraph of any of its representative. 
To see why this concept is independent of the representative
holds by definition:  any (spanning) c-subgraphs of some
representative coincides with some (spanning) c-subgraphs of
any another representative up to discs. The fact that 
one c-subgraph is spanning in some $\mathcal{G}$ 
means that it includes all vertices of $\mathcal{G}$. Removing all discs, it becomes spanning in $\mathcal{G}\setminus D_{\mathcal{G}}$,
for any $\mathcal{G}$.



\vspace{0.4cm}

\noindent{\bf Colored tensor graphs.} 
Apart from the stranded structure, 
the second important feature of the type of graphs 
which we will study is the coloring.

\begin{definition}[Colored and bipartite graphs]\label{def:colbi}
$\bullet$ A  $(D+1)$ colored graph is a graph 
together with an assignment of a color belonging to the set $\{0,\cdots,D\}$ to each of its edges
such that no two adjacent edges share same color.

$\bullet$ A bipartite graph is a graph whose set $\mathcal{V}$ of vertices 
is split into two disjoint sets, i.e. $\mathcal{V} = \mathcal{V}^+ \cup \mathcal{V}^-$
with $\mathcal{V}^+\cap\mathcal{V}^-= \emptyset$,  such that each edge
connects  a vertex $v^+ \in \mathcal{V}^+$ and a vertex
$v^- \in \mathcal{V}^-$. 

\end{definition}
We are in position to define a colored tensor
graph. 


\begin{definition}[Colored  tensor graph \cite{Gurau:2009tw,Gurau:2011xp}]\label{def:coltens}
A rank $D$ colored tensor graph $\mathcal{G}$ is a graph such that:
 
$\bullet$ $\mathcal{G}$ is $(D+1)$ colored and bipartite;

$\bullet$ $\mathcal{G}$ is a rank $D$ tensor graph. 

\end{definition}


The type of restriction introduced in Definition \ref{def:coltens}
allows us to have a control on the type of graphs 
 which are generated. 
This restriction is therefore useful to discuss a specific 
class of these graphs but still 
containing a large (infinite) number of them.

As an illustration, a rank 3 colored tensor graph is pictured
in Figure \ref{fig:colgraph}. Each vertex (looking like the $K_{4}$ complete graph again) is the dual of a tetrahedron and an edge represents a triangle endowed with a color $i \in \{0,1,2,3\}$. The graph is 
also bi-partite. 


We denote a rank $D$ colored tensor  graph as $\mathcal{G}(\mathcal{V},\mathcal{E})$
where, as usual, $\mathcal{V}$ is its set of vertices and
$\mathcal{E}$ is its set of edges. 
 In a rank $D$ colored tensor graph, to each pre-flag could 
be assigned a color so that an edge can only connect  
pre-flags of the same color. In such a situation, edges will inherit pre-flag
colors.  Equivalently, one could infer a color for each pre-flag
as the color of the edge touching this pre-flag. 
There are certainly 
more data worthwhile to be discussed in such  a graph.


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=5cm, height=3cm]{colgraph.pdf}
\vspace{0.1cm}
\caption{ {\small A rank 3 colored tensor graph.}}
\label{fig:colgraph}
\end{minipage}
\put(-175,-10){1}
\put(-175,25){2}
\put(-175,58){3}
\put(-175,90){0}
\end{figure}




\begin{definition}[$p$-bubbles \cite{Gurau:2009tw}]
\label{def:pbub}
A $p$-bubble with colors $i_1 < i_2 < \dots<i_p $, $p\leq D$,
and  $i_k\in \{0, \dots, D\}$ of a rank $D$ colored  tensor 
graph $\mathcal{G}$ is a maximally connected component 
made of strands of edges  of colors $\{i_1, \dots, i_p\}$. 
 \end{definition}

For any $D$,  vertices are 0-bubbles, edges 
are 1-bubbles. Restricting to $D=3$, there are 
two other types of $p$-bubbles that we shall need
in the following:

$\bullet$ The connected components of $\mathcal{G}$ made with two colors are cycles of lines along which the colors alternate. These are 2-bubbles called the faces of the graph  (See the face $f_{03}$ (in red) in  Figure \ref{fig:facebub}).

$\bullet$  A 3-bubble (or simply bubble in $D=3$) is a connected
component of the graph which has three colors
 (See Figure \ref{fig:facebub}). 

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=13cm, height=2.5cm]{bubbles.pdf}
\vspace{0.1cm}
\caption{ {\small The face $f_{03}$ (in red) and bubbles of the graph 
of Figure \ref{fig:colgraph}.}}
\label{fig:facebub}
\end{minipage}
\put(-315,-10){$f_{03}$}
\put(-232,-10){$\bee_{012}$}
\put(-146,-10){$\bee_{013}$}
\put(-75,-10){$\bee_{023}$}
\put(-5,-10){$\bee_{123}$}
\end{figure}

Faces of stranded graphs are made with strands 
of edges and vertices. We say that ``a face passes through 
an edge (or vertex) $x$ time(s)'' if it is built with $x\geq 0$ 
strands of this edge (or vertex). Of course, $x=0$, means
that the face never passes through the element. 

Remark that, importantly, having bicolored faces prevents
faces to pass more than once in an edge.
As in the definition of a face, any strand of the rank $D$ colored tensor
graph is also bicolored. This crucial feature 
will be used several times in the following.  


Any 3-bubble can be seen 
as a $2D$ ribbon graph. The vertices of a bubble are three valent
vertices obtained by decomposing  the vertex of the graph
in the way of Figure \ref{fig:facebub}.  
The edges of a 3-bubble are colored 
ribbon edges generated by the decomposition of
the colored edges of the rank $D$ colored graph. As ordinary 
ribbon graphs, 3-bubbles have faces as well. These faces
are endowed with a pair of colors like the faces of the initial graph. Thus a bubble is simply a rank 2 colored tensor graph
lying inside the rank 3 colored tensor graph. 
The set of 3-bubbles will be denoted by $\mathcal{B}_3$ and
$|\mathcal{B}_3| = B_3$. The index 3  will be omitted when 
discussing $D=3$. 


In the dual picture, a face is a  (boundary) surface
and a bubble is a collection of surfaces which close
and form a $3D$ region in the simplex. Often, one associates
directly the $3D$ region to the bubble. 


A rank $D$ colored tensor graph admits another equivalent  representation. By collapsing the entire rank $D$ colored tensor 
graph in the way previously mentioned, namely by forgetting its stranded structure, we obtain another representation 
of the same graph. This representation, called {\emph{compact}} in the following, is merely obtained by regarding the tensor graph as a simple bipartite colored graph in the sense of Definition \ref{def:colbi}.
It is worth underlining that 
one representation of the graph  determines unambiguously the other
(this is not the case for the collapsed graph which cannot fully characterize the stranded structure of its generating graph). 
For instance, the graph of  Figure \ref{fig:colgraph}
can be also drawn in the compact form of Figure \ref{fig:compak}.


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=2.5cm, height=1.5cm]{compak.pdf}
\vspace{0.1cm}
\caption{ {\small Compact representation of the graph of Figure \ref{fig:colgraph}.}}
\label{fig:compak}
\end{minipage}
\put(-175,-10){1}
\put(-175,12){2}
\put(-175,28){3}
\put(-175,45){0}
\end{figure}


Rank $D$ flags can be considered as well on rank $D$ colored tensor
graph, provided these flags possess a color and their gluing respects the graph coloring at each vertex. Thus to axioms (i') and (ii') of Definition
\ref{def:tens}, we add: 

{\it (iii') to each edge and flag, one  assigns a color $i \in \{0,1,\dots,D\}$.}

The cut of an edge can be done in the same sense of Definition 
\ref{def:cutedtens} for colored tensor graphs. 
The crucial point is solely to respect 
the color structure of the graph after the cut such that
each of resulting flags possess the same 
color structure of the former edge.  

The definitions of a rank $D$ colored tensor graph with flags 
$\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ (see Figure \ref{fig:tenfla}  for an illustration
for $D=3$) and its spanning c-subgraphs of $\mathcal{G}$ 
follow from spanning c-subgraphs of the stranded graph $\mathcal{G}$
and from Definition \ref{subfla}. The only point to be 
added is the color structure. The following is straightforward:

\begin{proposition}\label{prop:subcol}
(Spanning) c-subgraphs of a rank $D$ colored tensor 
graph are rank $D$ colored tensor graphs. 
\end{proposition}


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=12cm, height=2.5cm]{opentens.pdf}
\vspace{0.1cm}
\caption{ {\small An open rank 3 colored tensor graph 
and its bubbles; $f_{01}$ (highlighted in red) is an open face;
$\bee_{012}$, $\bee_{013}$ and $\bee_{123}$ are open bubbles and $\bee_{023}$ is closed.}}
\label{fig:tenfla}
\end{minipage}
\put(-350,33){1}
\put(-312,-10){2}
\put(-312,45){3}
\put(-312,75){0}
\end{figure}



Let us come back to the elements of the graphs. 
An edge $e$ is called bridge if $\mathcal{G} \vee e$ becomes disconnected. 
There is no self-loop at this moment.  

As in the case of ribbon graphs with flags, introducing tensor
graphs with flags requires a special treatment for faces. 
Using Definition \ref{pinch}, faces can be open or
closed connected components if they pass through external points
or not. An open face with color pair (01) is highlighted in red in Figure \ref{fig:tenfla}. 
The sets of closed and open faces will be denoted by $\mathcal{F}_{{\rm int}}$
and $\mathcal{F}_{{\rm ext}}$, respectively. 
Hence, for a rank $D$ colored graph with flags, the set  $\mathcal{F}$ of faces is the disjoint union $\mathcal{F}_{{\rm int}} \cup \mathcal{F}_{{\rm ext}}$.
The notion of 
closed or open rank 3 colored tensor graph can be reported
accordingly if $\mathcal{F}_{{\rm ext}}=\emptyset$ or not, respectively. 

A bubble is open or external if it contains open faces otherwise
it is  closed or internal. Open and closed bubbles for a rank 3 colored
tensor graph with flags given in Figure \ref{fig:tenfla} have been illustrated therein.  The sets of closed and open bubbles will be denoted by $\mathcal{B}_{{\rm int}}$ and $\mathcal{B}_{{\rm ext}}$, respectively.


The notions of pinched graph $\widetilde{\mathcal{G}}$ and of boundary graph is of great 
significance and we can address the pinching procedure colored tensor graph with flags. First, pinching a tensor flag  can be defined
by the identification of the external points of the flag.
The pinched graph $\widetilde{\mathcal{G}}(\widetilde{\mathcal{V}},\widetilde{\mathcal{E}},\widetilde{\mathfrak{f}}^0)$ is a closed
graph obtained from $\mathcal{G}$ after pinching of all 
of its flags and still the following relations 
are valid
\begin{equation}
\widetilde{\mathcal{V}} = \mathcal{V}\,, \qquad  \widetilde{\mathcal{E}} = \mathcal{E}\,, 
\qquad  |\widetilde{\mathfrak{f}}^0| = |\mathfrak{f}^0|\,.
\end{equation}

\begin{definition}[Boundary tensor graph]
\label{def:bgph}
$\bullet$ The boundary graph $\partial{\mathcal{G}}({\mathcal{V}}_{\partial},{\mathcal{E}}_{\partial})$ of a rank $D$ colored 
tensor graph $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ is a graph obtained by inserting a vertex 
with degree $D$ at each additional flags of $\mathcal{G}$ and taking the external 
faces of $\mathcal{G}$ as its edges. Thus, $|{\mathcal{V}}_{\partial}| = |\mathfrak{f}^0|$ and 
${\mathcal{E}}_{\partial} = \mathcal{F}_{{\rm ext}}$. 

$\bullet$ The boundary of a closed rank $D$ colored tensor graph
is empty. 
\end{definition}


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=3cm, height=2cm]{boundary3.pdf}
\vspace{0.1cm}
\caption{ {\small Boundary graph (in dashed lines) of the graph of Figure \ref{fig:tenfla}.}}
\label{fig:bound3}
\end{minipage}
\put(-210,33){1}
\put(-140,33){1}
\put(-175,-10){2}
\put(-175,35){3}
\put(-175,60){0}
\end{figure}


The boundary of a tensor graph without colors
is obtained in the same way as defined above
since  the colored feature of the graph is not used
in the definition. To the graph of Figure \ref{fig:tenfla},
we associate its boundary  depicted in Figure \ref{fig:bound3}.

The dual of rank 3 colored tensor graph with flags is nothing but
a 3D simplicial complex with tetrahedra (as vertices) made with colored triangles having a colored 2D boundary \cite{Gurau:2009tz}. This colored boundary surface is obtained by gluing colored triangles dually associated with colored flags.  

Let us stress that the boundary graph  $\partial{\mathcal{G}}$ of a rank $D$ (colored or not) tensor graph $\mathcal{G}$ encodes, in the dual picture,  
the triangulation of the boundary of the $D$ simplicial complex
dual to $\mathcal{G}$. 
In the specific instance of 3D,  $\partial{\mathcal{G}}$ represents
a 2D triangulation of the boundary of a 3-simplicial complex
dual to $\mathcal{G}$. In the same vein that colors improve the
topology of the triangulated object associated with  $\mathcal{G}$, a colored boundary graph $\partial{\mathcal{G}}$ improves the regular feature
of the boundary manifold for that triangulated object.
The construction of boundary graph $\partial{\mathcal{G}}$  by Definition 
\ref{def:bgph} should be nothing but a compact representation of 
a more elaborate graph which can encode the triangulation
of a surface. We first need another type of colored structure 
for graphs in order to discuss this. 
\begin{definition}[Ve-colored graphs]\label{def:2colbi}
$\bullet$ A  $(D+1)$ ve-colored graph is a graph such that to each vertex
is assigned a color in $\{0,\dots,D\}$ and to each edge is assigned a pair $(ab)$ of colors, $a,b$ in $\{0,\dots,D\}$, $a\neq b$, such that 

- either the edge is incident to vertices with the same color $c$,
in this case, $a$ (or $b$) equals $c$ and $b\in \{0,\dots,D\} \setminus \{a\}$ (respectively, $a\in \{0,\dots,D\} \setminus \{b\}$);

- the edge is incident to vertices with different colors
 $a$ and $b$ 

\noindent
and such that  two adjacent edges cannot share 
the same couple of colors. 
\end{definition}

Some 4 ve-colored graphs are drawn in Figure \ref{fig:vecolor}.

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=7cm, height=2.5cm]{vecolor.pdf}
\vspace{0.1cm}
\caption{ {\small Examples of 4 ve-colored graphs.}}
\label{fig:vecolor}
\end{minipage}
\end{figure}

One notices that a $(D+1)$ ve-colored graph is a $D(D+1)/2$ colored
graph for edges equipped color pairs $ab$, $a<b$, chosen in 
$\{01,02, \dots, 0D, 12,\dots, D(D-1)\}$. Thus in a ve-colored graph there is no
self-loops. 

\begin{definition}[Ve-colored  tensor graph]\label{def:2coltens}
A rank $D$ ve-colored tensor graph $\mathcal{G}$ is a graph such that:
 
$\bullet$ $\mathcal{G}$ is $(D+2)$ ve-colored;

$\bullet$ $\mathcal{G}$ is a rank $D$ tensor graph. 

\end{definition}




The following statement holds. 

\begin{proposition}[Color structure of $\partial{\mathcal{G}}$ \cite{Gurau:2009tz}]
The boundary graph $\partial{\mathcal{G}}({\mathcal{V}}_{\partial},{\mathcal{E}}_{\partial})$ of a rank $D$ colored 
tensor graph $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ is a rank $(D-1)$ ve-colored tensor graph.
\end{proposition}
\proof The colors of vertices in $\partial{\mathcal{G}}$ inherits  the colors
of the flags of $\mathcal{G}$. 
The edge coloring should clearly coincide with 
the external face coloring defined by a couple $(ab)$. 
At one flag, the  color pairs of any external face
never coincide. This makes the graph 
$\partial{\mathcal{G}}$ as $(D+1)$ ve-colored. To construct the extra 
tensor structure on $\partial{\mathcal{G}}$, one expands its vertices
and edges into stranded vertices with fixed coordination 
$D$ and edges with $D-1$ parallel strands. The connecting
pattern of the pre-flags of its vertices follows the one of
the complete graph $K_{D}$.  The proposition  follows. 

\qed 

For instance in 3D, each vertex of $\partial{\mathcal{G}}$ 
is colored and is three valent. Each edge of $\partial{\mathcal{G}}$ is a bicolored
ribbon. See Figure \ref{fig:boundtens3}. 


\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=7cm, height=2cm]{bouten3.pdf}
\vspace{0.1cm}
\caption{ {\small Rank 2 ve-colored stranded structure of the boundary
graph of Figure \ref{fig:bound3}.}}
\label{fig:boundtens3}
\end{minipage}
\put(-155,25){1}
\put(-280,25){1}
\put(-223,-10){12}
\put(-223,33){13}
\put(-223,60){10}
\put(-135,25){1}
\put(-65,25){1}
\put(-102,5){\small{12}}
\put(-102,32){\small{13}}
\put(-102,47){\small{10}}
\end{figure}


\begin{remark}\label{rem:1} Importantly, any face of the boundary graph coincide
with a connected component of the boundary $\partial \bee_{aa_1a_2}$ of some open bubble $\bee_{aa_1a_2}$ viewed as an open ribbon graph. Indeed, any (closed) face of a boundary graph is made with strands coming from open faces belonging necessarily 
to open bubbles. The boundary graph being closed, in order
to get all of its faces, one has first to pinch all external 
bubbles $\bee$, yielding $\widetilde\bee$, and collect closed faces 
coming uniquely from the pinching as performed in Proposition \ref{pinbor}. \end{remark}
As an illustration of the above remark, consider the graph $\mathcal{G}$ Figure \ref{fig:tenfla} with 
boundary $\partial{\mathcal{G}}$ drawn in Figure \ref{fig:bound3}. Let us pick
the face $f_{012}$ of $\partial{\mathcal{G}}$ and consider the open
bubble $\bee_{012}$ and its pinched version $\widetilde\bee_{012}$. 
The closed face $\widetilde f_{012}$ of $\widetilde\bee_{012}$ 
coincide with $f_{012}$. Furthermore, any such closed face cannot
belong to two different pinched bubbles by color exclusion
and by the fact that there are only two bubbles passing 
through an edge which could use a given edge strand.


\subsection{W-colored stranded graphs}
\label{subset:wgraphs}

It has been discussed in length that the contraction 
of an edge in a tensor colored graph yields another
type of graph for which neither the color  (Definition \ref{def:colbi})
nor the tensor axioms (Definition \ref{def:tens}) 
apply \cite{Gurau:2009tz}.
In order to define the topological polynomial and circumvent such an odd feature of tensor graphs,
some proposals have been made to redefine the notion 
of contraction of an edge or redefine subgraphs
for which the contraction applies \cite{Gurau:2009tz,Tanasa:2010me}. 

Using  Definition \ref{def:constran},  we can now 
contract any rank $D$ edge provided the fact that we are working in the extended
framework of stranded graphs. This definition therefore
applies to a colored tensor graph. Our task  is to 
characterize the new class of stranded graph 
obtained after an edge contraction of a colored tensor graph. 
From now on edge contraction means always soft edge contraction
in the sense  Definition \ref{def:constran}.


The contraction of an edge $e$ in a rank $D$ colored tensor graph $\mathcal{G}$ (possibly with flags) yields a rank $D$ stranded graph $\mathcal{G}/e$ obtained from $\mathcal{G}$ by the procedure described in Definition \ref{def:constran}
 and respecting the coloring. 
By respecting the coloring, we understand that edges 
which are not contracted keep their color
and all strands keep their color pair. 
For a rank $D$ colored tensor graph, 
it is straightforward to see that any edge contraction in $\mathcal{G}$ brings 
in  $\mathcal{G}/e$ a vertex possessing at least two pre-flags of the same color (see an example in $D=3$ in Figure \ref{fig:contens}). 
This  breaks the color axiom on vertices since it allows that
edges with the same color to be branched on the same vertex. 
But still in $\mathcal{G}/e$ there is a color structure defined in a 
sense weaker than Definition \ref{def:colbi}. Such a colored
structure is mainly based on the feature that any
edge contraction preserves strands and their color pair.



\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=7cm, height=2cm]{contractens.pdf}
\vspace{0.1cm}
\caption{ {\small Contraction of an edge in a rank 3 colored tensor 
graph with flags.}}
\label{fig:contens}
\end{minipage}
\put(-188,25){1}
\put(-280,25){1}
\put(-233,-5){2}
\put(-233,33){3}
\put(-233,55){0}
\put(-125,25){1}
\put(-68,25){1}
\put(-95,-10){2}
\put(-95,60){0}
\end{figure}
 

In the following, we first spell out the object of interest as
defined by the result of the contraction of a rank 
$D$ colored tensor graph. Then we find a characterization
of it. 

\begin{definition}[Rank $D$ w-colored graph I]
A rank $D$ weakly colored  or w-colored graph is the equivalence class
(up to trivial discs)
of a rank $D$ stranded graph obtained by successive edge contractions of some rank $D$ colored tensor graph. 
\end{definition}

The equivalence class of any rank $D$ colored tensor graph
up to trivial discs is a rank $D$ w-colored graph.  
This holds by convention when no contraction is performed.
 Another property is that several rank $D$ colored tensor graphs
may have the same contracted graph. Hence to one
rank $D$ w-colored graph may correspond several 
rank $D$ colored tensor graphs which could generate it. 
On the other hand, the existence of a representative $\mathcal{G}$
of some  rank $D$ w-colored graph $\mathfrak{G}$ as being 
 the contraction of some rank $D$ colored tensor graph
does not imply necessarily that any other representative
 results from a graph contraction. 
Given $\mathcal{G}$ the representative of $\mathfrak{G}$ and
$\mathcal{G}_\text{color}$ the rank $D$ colored tensor graph 
which gives $\mathcal{G}$ after contraction, let us
assume that this contraction yields $\ell_0$ extra discs
with particular bi-colored strands. Any representative $\mathcal{G}'$ of $\mathfrak{G}$,
$\mathcal{G}'$ could come from the contraction of a
 rank $D$ colored tensor graph $\mathcal{G}'_\text{color} \sim \mathcal{G}_\text{color}$ 
if the number $k$ of discs of $\mathcal{G}'$ is larger 
than $\ell_0$, in which case $\mathcal{G}'_\text{color} = (\mathcal{G}_\text{color}\setminus D_{\mathcal{G}_\text{color}})
\cup D_{k - \ell_0}$, where $D_{k - \ell_0}= D_{\mathcal{G}'} \setminus D_{\ell_0}$
and where $D_{\ell_0}$ is the set of additional discs coming uniquely 
from the contraction of $\mathcal{G}_\text{color}/D_{\mathcal{G}_\text{color}}$. One should pay attention of the type of color pairs that should occur 
on discs of $\mathcal{G}'$ to match with the color pairs of discs obtained
after contractions.  
  
It is relevant to discuss in greater detail the type of (non trivial) vertices that will generate any representative of any rank $D$ w-colored graphs.  To address this, we observe the following result from Lemma 
3 in \cite{BenGeloun:2011rc} and slightly adapted to the present context.

\begin{lemma}[Full contraction of a tensor graph]
\label{lem:fullcont}
$\bullet$ Contracting an edge in a rank $D$ (colored) tensor graph
does not change its boundary. 
$\bullet$ The contraction of all edges in arbitrary order of a rank $D$ (colored) tensor graph $\mathcal{G}$ yields a graph $\mathcal{G}^0$ defined by the boundary $\partial{\mathcal{G}}$ up to additional discs. 
\end{lemma}
\proof Contracting one edge in $\mathcal{G}$, 
all flags and all external faces remain untouched, 
and no other external face can be created by such a move
(we remove all present inner faces
and all remaining faces get shorter but are never cut). Hence for the resulting stranded graph 
$\mathcal{G}/e$, one has $\partial (\mathcal{G}/e)= \partial{\mathcal{G}}$. 
By iteration, contracting all edges of $\mathcal{G}$ in arbitrary order, the resulting graph $\mathcal{G}^0$ should contain $\partial{\mathcal{G}}$ as its boundary. But contracting all edges of $\mathcal{G}$, one obtains a single vertex graph 
per connected component plus trivial discs and no other closed faced left otherwise it would mean that there exist still edges where these closed
faces pass.  Hence necessarily $\mathcal{G}^0$ is nothing but a graph
made only with vertices (without edges) defined therefore by  $\partial{\mathcal{G}}^0= \partial{\mathcal{G}}$
up to trivial discs. 

\qed


Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ be a connected rank $D$ colored tensor graph
with a nonempty set of flags, $\mathfrak{f}^0\neq \emptyset$.
After a full contraction of all edges of $\mathcal{G}$, Lemma 
\ref{lem:fullcont} tells us that the end result is totally encoded in the boundary graph $\partial{\mathcal{G}}$ up to some discs.
This graph $\mathcal{G}^0$ appears  as one or a collection of rank $D$ stranded vertices $v_{\partial{\mathcal{G}};k}$, $k$ parametrizing the number of connected components of $\partial{\mathcal{G}}$. Note that if $\mathfrak{f}^0 = \emptyset$ then 
there is no boundary in $\mathcal{G}$ and $v_{\partial{\mathcal{G}}}$ is empty. 

Consider a stranded graph made with such vertices $v_{\partial{\mathcal{G}}_i;k_i}$ for a
finite family of boundaries $\partial{\mathcal{G}}_i$ of some connected rank $D$ colored tensor graphs $\mathcal{G}_i$ with a nonempty set of flags, $i\in I$, $I$ finite. In order to glue these vertices, one needs edges of rank $D$. 

\begin{proposition}[Rank $D$ w-colored stranded graphs II]
\label{def:weak}

A rank $D$ stranded graph $\mathcal{G}$ is a representative of a rank $D$ w-colored graph $\mathfrak{G}$ if and only if it satisfies 
\begin{enumerate}
\item[(i'')] vertices $v_i$ of $\mathcal{G}$ attached with flags are
graphs $V_i$ coming from the boundaries $\partial{\mathcal{G}}_i$ of a family of connected rank $D$ colored tensor graph $\mathcal{G}_i(\mathcal{V}_i,\mathcal{E}_i,\mathfrak{f}_i^0)$ with $\mathfrak{f}_i^0 \neq  \emptyset$. All pre-flags of $\mathcal{G}$ have a fixed cardinal $D$;


\item[(ii')] the edges of $\mathcal{G}$ are of rank $D$ and with parallel 
strands;

\item[(iii')] to edges and flags of $\mathcal{G}$ are assigned a color $\in \{0,1,\dots, D\}$
inherited from the pre-flags of the $v_i$'s. 

\end{enumerate}
\end{proposition}

\proof  
Let us consider the representative $\mathcal{G}$ of a rank $D$ w-colored graph 
$\mathfrak{G}$ and $\mathcal{G}_{\text{color}}$ a rank $D$ colored tensor graph 
the contraction of which yields $\mathcal{G}$. 
Let us pick another representative $\mathcal{G}'$ of $\mathfrak{G}$. 
Properties (ii'') and (iii')  for edges and flags of $\mathcal{G}'$ are trivially satisfied. 

Next, observe that to any rank $D$ colored tensor graph 
corresponds a rank $D$ w-colored tensor graph which 
is the  class of this same graph. 
Hence if $\mathcal{G}$ contains the vertices $v_0$
and $\bar v_0$ (from bi-partite property) of ordinary colored tensor graphs,
we can define these two vertices as the boundaries of the graphs defined by themselves attached with flags; the cardinal of their pre-flags is fixed to $D$ by definition. It is obvious that if $v_0$ and $\bar v_0$
(which are not trivial discs) are in $\mathcal{G}$ they are also in $\mathcal{G}'$ and so the same construction applies
to $\mathcal{G}'$.

Any vertex $v$ in $\mathcal{G}$ which is not a disc and not of the form of 
$v_0$ and $\bar v_0$  comes necessarily from some contractions
of some subset $\{e_l\}_{l\in I_v}$ of edges  in $\mathcal{G}_{\text{color}}$.  
Note that for all $v$, $\{e_l\}_{l\in I_v}$ should define
a partition of edges of $\mathcal{G}_{\text{color}}$ which do not belong
to $\mathcal{G}$. 
Consider the c-subgraph $\mathcal{G}_v$ in $\mathcal{G}_{\text{color}}$ defined by 
$\{e_l\}_{l\in I_v}$ and their end vertices. 
By Proposition \ref{prop:subcol}, $\mathcal{G}_v$ is a rank $D$ colored
tensor graph. Then, 
after the full contraction of all the $e_l$'s, by Lemma \ref{lem:fullcont}, 
we obtain $\partial{\mathcal{G}}_v$ up to some discs. $\partial{\mathcal{G}}_v$  also coincides with 
the new vertex $v$ in $\mathcal{G}$ attached with flags. 
Proceeding by iteration 
on all vertices of the representative $\mathcal{G}$, we 
get a family of rank $D$ colored of c-subgraphs $\mathcal{G}_v \subset  \mathcal{G}_{\text{color}}$, the overall contraction of which yields 
the vertices $v$ (plus flags) of $\mathcal{G}$ up to some trivial discs. The cardinal of all present
pre-flags is obviously fixed to $D$. 
Any vertex $v$ in $\mathcal{G}$ which is not a disc is also present in $\mathcal{G}'$ therefore all vertices of $\mathcal{G}'$ come from boundaries of some
families of colored graphs. 


Now consider a rank $D$ stranded graph $\mathcal{G}$ satisfying  (i''), (ii') and (iii') and its equivalence class $\mathfrak{G}$. 
Then by replacing in $\mathcal{G}$ all the vertices $v_i$ by 
the colored graphs $\mathcal{G}_i$ and respecting the coloring, we obtain
a rank $D$ colored tensor graph $\mathcal{G}_{\text{color}}$. Contracting
 in $\mathcal{G}_{\text{color}}$ all edges in all $\mathcal{G}_i$'s yields again the $v_i$'s 
determined by their boundary (Lemma \ref{lem:fullcont}), 
up to some discs. 
Thus the end result $\mathcal{G}'$ of these edge contractions is $\mathcal{G}$
 up to some discs therefore belongs to $\mathfrak{G}$. Hence $\mathfrak{G}$ is a rank $D$ w-colored graph. 


\qed 

From now on, since the rank of edges, flags and pre-flags is fixed to $D$, we omit to mention it. Thus, when no confusion may occur, 
rank $D$ colored tensor graph are named colored graphs and rank $D$ w-colored graphs are named w-colored graphs. 

The key notion of interest here pertains again to the
spanning c-subgraphs for a  w-colored graph. 
This notion has been already mentioned for equivalent classes, 
the sole new point  here is to add colors. 


\begin{proposition}[c-subgraph]\label{prop:classc}
Let $\mathfrak{G}$ be a  rank $D$ w-colored graph. The c-subgraphs of $\mathfrak{G}$ admit a rank $D$  w-colored  graph structure. 
\end{proposition}
 \proof  Consider $\mathfrak{G}$ a w-colored graph and
$\mathcal{G}$ the representative in $\mathfrak{G}$ obtained after contraction
 of some colored graph $\mathcal{G}_\text{color}$. 
Let $\mathfrak{g} \subset \mathfrak{G}$ be a c-subgraph of $\mathfrak{G}$. 
For any such $\mathfrak{g}$, we shall show that there exists a 
subgraph $g$ of $\mathcal{G}$ such that $g$ is a representative of
$\mathfrak{g}$. Then the proof will be complete because $g$ is exactly 
the colored graph that we seek since it comes from a contraction of
some subgraph of $\mathcal{G}_\text{color}$ admitting itself a colored structure
by Proposition \ref{prop:subcol}. 
Now, the existence of $g$ is guaranteed by the following. 
Choose any representative $g'$ of $\mathfrak{g}$ in any $\mathcal{G}'$, then 
$g'$ is a  c-subgraph in $\mathcal{G}'$. From $g'$, 
we built $\tilde g = g'\setminus D_{g'}$ which is a c-subgraph of $\mathcal{G}$.
Expanding $\tilde g \subset \mathcal{G}$ back in $\mathcal{G}_\text{color}$, we get 
a colored c-subgraph of $\mathcal{G}_\text{color}$ the contraction of which yields finally 
a c-subgraph $g$ of $\mathcal{G}$. To see that $g \sim g'$ is direct 
since $g \sim \tilde g$.


\qed 


We give now few more properties of the vertices of 
representatives of rank $D$ w-colored graphs. First, 
 there are infinitely many vertices 
for these graphs. However, some constraints should be 
imposed on vertices for being the boundaries of some rank $D$ colored tensor graphs. 

\begin{lemma}\label{lem:parity}
Consider a rank $D$ w-colored graph with 
representative made with a vertex with $N$ pre-flags. If $D$ is odd 
then $N$ should be always even. 
\end{lemma}
\proof This simply holds from the fact that the number $ND$ of 
pre-flag points in the vertex considered of 
the representative  should be even in order to properly form bows.

\qed

For rank $D$ tensor graphs, the above lemma is
obvious since  $N$ is always fixed to $D-1$. 
The point of the above proposition is to establish that
a vertex of rank $D$ w-colored graph can be of arbitrary 
degree but with even parity in odd dimension. 

The next lemma follows arguments given in  Lemma 2.1 in \cite{Geloun:2009pe} (as a dictionary, external legs in quantum field theory corresponds to flags). For sake of completeness, 
let us restate this proposition in the present language. 

\begin{lemma}[Lemma 2.1 in \cite{Geloun:2009pe}]
\label{lem:miss}
Given a rank $D$ colored tensor graph with $n$ vertices 
and $N$ flags. If one color is missing on its flags, then 

- $n$ is an even number 

- the number $N$ of flags is even 
and the colors of flags should appear in pair.
\end{lemma}
\proof  
If one color, say $a$, is missing on the flags, it means that 
 $a$ appear only on edges. Each edge occupies
two pre-flags of the same color and that one has $n$ 
pre-flags of each color. Now since $a$ should only appear 
on edges, it follows that the $n$ pre-flags of color $a$ 
should be all paired to give edges. This proves the first point. 

We henceforth know that $n$ is even. Assuming that
there is an odd number of flags possessing a particular color,
this implies that the number of pre-flags with that
color which should be paired for making edges would be 
odd as well, hence would be impossible. 
The second point follows. 

\qed

Lemma \ref{lem:miss} entails other properties of the vertices
of representatives of a w-colored graph. Indeed, we infer from this statement
that the vertices in a rank $D$ w-colored graph can be only 
of some types. Some vertices attached with flags have been depicted in Figure 
\ref{fig:w-vert} using the compact representation. Note that, in contrast
with colored graphs, the compact notation becomes ambiguous for general w-colored graphs. We use it here for displaying the color feature of the different flags attached to the vertices. 
For convenience, we also introduce the following notation:
 each pre-flag $f$ may have a color 
$a$ or $\bar a$ which is reminiscent of the fact that 
 $a$ and $\bar a$ come from different types of vertices
in some bipartite graph. 
We call $a$ and $\bar a$ {\bf conjugate} colors
and call conjugate flags, the flags which possess $a$ and $\bar a$ 
as colors. 

 When a vertex has uniquely one pair of conjugate colors $a$ and $\bar a$ for all pre-flags,
it is related to a so-called tensor unitary invariant object 
\cite{Gurau:2012ix}. We call it a 1-color vertex. 
When the vertex has 2 conjugate color pairs, $2<D$, then 
it can be seen as a gluing of two 1-color vertices $v_1$ and $v_2$ after cutting some bows in $v_1$ and $v_2$ and then gluing these 
(still respecting the coloring). Then one may 
figure out that the trace invariant object above gets a weaker
sense because the invariance is broken in some sector (induced by 
the cut bows). For more colors, one proceeds by iteration
gluing two 1-color vertices and then gluing the result
with another 1-color vertex with a different color. 
Performing such a gluing is possible up to a number of $D-1$ colors. 
Though beyond the scope of this work, an interesting task would be to count the number of such $2,3,\dots, D-1$ w-colored vertices
for a fixed number $N$ of flags. 
For the last type of vertices with all $D$ colors, it does not
necessarily follow from the gluing of 1-color vertices. 
The same counting will become highly non trivial,  
if exists. 

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=7cm, height=3.5cm]{w-vertice.pdf}
\vspace{0.1cm}
\caption{ {\small Some vertices of w-colored graphs.}}
\label{fig:w-vert}
\end{minipage}
\put(-238,80){$\bar 1$}
\put(-276,80){1}
\put(-201,102){0}
\put(-222,80){1}
\put(-180,80){3}
\put(-201,53){2}
\put(-146,102){$\bar 0$}
\put(-167,80){$\bar 3$}
\put(-125,80){$\bar 1$}
\put(-145,53){$\bar 2$}
\put(-90,102){$a$}
\put(-112,80){$\bar a$}
\put(-69,80){$b$}
\put(-89,53){$\bar b$}
\put(-235,17){$a$}
\put(-280,17){$\bar a$}
\put(-272,34){$b$}
\put(-258,38){$\bar b$}
\put(-240,-1){$\bar c$}
\put(-257,-7){$c$}
\put(-222,17){$a$}
\put(-180,17){$2$}
\put(-214,34){$0$}
\put(-200,38){$3$}
\put(-184,-1){$1$}
\put(-199,-8){$\bar a$}
\put(-167,17){$a$}
\put(-123,17){$\bar 3$}
\put(-160,34){$\bar 0$}
\put(-145,38){$\bar 1$}
\put(-130,34){$\bar 2$}
\put(-129,-1){$\bar b$}
\put(-144,-8){$b$}
\put(-160,-1){$\bar a$}
\put(-112,17){$\bar 0$}
\put(-70,17){$3$}
\put(-105,34){$\bar 1$}
\put(-90,38){$\bar 2$}
\put(-75,34){$\bar 3$}
\put(-74,-1){$2$}
\put(-90,-9){$ 1$}
\put(-105,-1){$ 0$}
\end{figure}
 







\begin{lemma}\label{lem:internal}
Let $e$ be a regular edge or a bridge with end vertices $v_1$ and 
$v_2$ of any representative of a rank  $3$ w-colored 
graph. Contracting $e$ in the representative yields a new vertex $v$ which is connected. 
\end{lemma}
\proof
Consider $e$ which is not a self-loop, $e$ is common to all $\mathcal{G}$ representative of a rank 3 w-colored graph. Its strands join in $v_1$
and in $v_2$ a collection of connected families of pre-flags. 
The initial vertices $v_1$ and $v_2$ being connected, 
 two different cases may occur:

(i) All strands of $e$ are connected
to a unique pre-flag either in $v_1$ 
or $v_2$. This implies that there are just two pre-flags in $v_1$
or in $v_2$. Contracting $e$, the vertex $v$ obtained is connected. 

(ii) Assume now that attached to each strand
of $e$, we have $d$ families 
of connected pre-flags in $v_1$ or in $v_2$, $2\leq d\leq 3$ (see an illustration in Figure \ref{fig:lembrid}). 
This is enforced by the coloring which 
prevents faces to pass through $e$ more than once. If contracting $e$ 
gives a disconnected vertex then, in each $v_1$ and $v_2$, 
the connected families of pre-flags do not have any bow between them\footnote{Note that this is only 
a necessary condition for obtaining a disconnected vertex.}. 
Notice that there is necessarily at least one connected family of 
pre-flags joining $e$ by a unique 
bow $b$. For such a family $\xi$, all pre-flags are fully connected via bows and there is a unique pre-flag point, the one related to $e$ via $b$,
not linked to any other pre-flag in $\xi$. By an argument
of parity, we aim at showing that it is impossible. 



\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=4cm, height=2cm]{lembrid.pdf}
\vspace{0.1cm}
\caption{ {\small Families $F_1, F_2$ and $F_3$ of connected pre-flags
attached to each strand of a non self-loop edge.}}
\label{fig:lembrid}
\end{minipage}
\put(-238,55){$F_1$}
\put(-245,25){$F_2$}
\put(-233,0){$F_3$}
\put(-160,35){$e$}
\end{figure}

For simplicity, let us fix that $e$ is of color $0$ and that
the strand $s$ of color pair $(01)$ in $e$ touches the connected and separate family $\xi$ a pre-flag $f$. Two cases may occur: either
$f$ is of color  $1$ or of color $\bar 0$. 

(A) If $f$ of color $1$: 
Denote $N_i$ and $\bar N_i$ the number of pre-flags in $\xi$
of color $i=0,1,2,3$ and $\bar i=\bar 0,\bar 1,\bar 2,\bar 3$, respectively. There are exactly 
$N_i + \bar N_i$ pre-flag points labeled by color pairs $(ij)$, 
 $i=0,2,3$, $j \in \{0,1,2,3\}$ but $j\neq i$. These
points come from pre-flags of colors $0,2,3$ and 
$\bar 0, \bar 2,\bar 3$. 
Meanwhile, there are 
$(N_1-1) + \bar N_1$ pre-flag points of color pairs $(01)$, 
and $N_1 + \bar N_1$ of color pairs $(1j)$, $j \in {2,3}$.  
These last points come uniquely from pre-flags with color $1$ and
$\bar 1$. 
Assuming that all pre-flag points but one in $\xi$ should be totally
connected by bows implies the following equations:
\begin{eqnarray}
&&
N_0 + \bar N_0 + (N_1-1) + \bar N_1 = 2k^{01} \,,\crcr
&&
N_0 + \bar N_0 + N_2 + \bar N_2 = 2k^{02} \,,\crcr
&&
N_0 + \bar N_0 + N_3 + \bar N_3 = 2k^{03} \,,\crcr
&&
N_1 + \bar N_1 + N_2 + \bar N_2 = 2k^{12} \,,\crcr
&&
N_1 + \bar N_1 +  N_3 + \bar N_3= 2k^{13} \,,\crcr
&&
 N_2 + \bar N_2 +  N_3 + \bar N_3= 2k^{23} \,,
\label{paring}
\end{eqnarray}
for some $k^{ij}$ positive integers counting the number
of bow with colors $(ij)$. It is simple to 
show that this system leads to the inconsistent equation
\begin{eqnarray}
2(N_0 + \bar N_0) +2 (k^{12}  -  k^{02}) -1 = 2k^{01}\,.
\end{eqnarray}


(B) If $f$ is of color $\bar 0$:
 $N_0+ (\bar N_0 -1)$ becomes the number of pre-flag points
of color pairs $(01)$ in $\xi$ induced by pre-flags of 
color $0$ and $\bar 0$ and $N_1 + \bar N_1$
is the number of pre-flags points of colors $01$ induced by 
pre-flags of color $1$ and $\bar 1$.
This is the same as switching the role of $1$ and $\bar 0$ 
in the above case.
The above system holds again as constraints on the 
number of pre-flag points and yields the same  conclusion. 

\qed

The above lemma should  clearly  admit an extension 
to any dimension $D$ by partitioning $D$ and analyzing 
the connection of the strands of $e$ and the connected 
pre-flag families. We do not need however such a stronger
and much technical result for the following. 

In contrast,  the contraction of a self-loop may disconnect the vertex. 
 In any case, since self-loop graphs are terminal forms,
a special treatment for them is required. 


The whole construction above is mainly made in order
to maintain the consistency of the $p$-bubble definition. For instance,
edges are still 1-colored objects, (closed and open) faces are bicolored connected objects,  (closed and open) 
3-bubbles are connected objects with 3 colors.
However,  3-bubble are no longer built uniquely with three valent vertices.  They can be made with vertices with lower or greater valence as illustrated in Figure \ref{fig:npb}.  
In any case, Definition \ref{def:pbub}
is still valid and we shall focus on this. 



\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=8cm, height=2cm]{newpbubb.pdf}
\vspace{0.1cm}
\caption{ {\small Two bubbles graphs $\bee_1$ and $\bee_2$ of 
$\mathcal{G}_1$ and $\mathcal{G}_2$, respectively: $\bee_1$ has a vertex with valence 2 
and $\bee_2$ a vertex with valence 4.}}
\label{fig:npb}
\end{minipage}
\put(-265,0){$\mathcal{G}_1$}
\put(-213,0){$\bee_1$}
\put(-240,25){$0$}
\put(-295,25){$\bar 0$}
\put(-133,-10){$\mathcal{G}_2$}
\put(-73,-10){$\bee_2$}
\put(-158,25){$0$}
\put(-108,25){$\bar 0$}
\end{figure}



\begin{lemma} \label{lem:cutmg}
Let $\mathcal{G}$ be a representative of $\mathfrak{G}$ a rank $D$ w-colored graph. 
$\bullet$
Cutting an edge $e$ in $\mathcal{G}$ yields a representative $\mathcal{G} \vee e$ of another rank $D$ w-colored graph denoted $\mathfrak{G} \vee e$.  
$\bullet$
Contracting an edge $e$ in $\mathcal{G}$ yields a representative $\mathcal{G}/e$ of another rank $D$ w-colored graph denoted $\mathfrak{G}/e$. 
  \end{lemma}
\proof  Let $e$ be an edge in $\mathcal{G}'$ representative of 
some w-colored graph $\mathfrak{G}$ and  $\mathcal{G}$ the representative
of $\mathfrak{G}$ resulting from a contraction of some colored graph 
$\mathcal{G}_\text{color}$. 

The cut graph $\mathcal{G}' \vee e$ is equivalent to $\mathcal{G} \vee e$.
We use again here the expansion and contraction 
move: starting from $\mathcal{G} \vee e$, we expand this graph in $\mathcal{G}_\text{color} \vee e$ and contract it back to nothing but itself. One finds that $\mathcal{G}\vee e$ is therefore a graph resulting from the contraction of a colored graph. 
Its equivalence class is the w-colored graph desired. 

Contracting now $e$ in $\mathcal{G}'$,  one gets a graph $\mathcal{G}'/e$ equivalent
to $\mathcal{G}/e$. There exists a colored graph $\mathcal{G}^0_\text{color}$ contracting
to $\mathcal{G}/e$. This is nothing but $\mathcal{G}_\text{color}$ on which after all 
contraction yielding $\mathcal{G}$, one perform another contraction
on $e$. Note that we could have defined $\mathcal{G}^0_\text{color} = \mathcal{G}_\text{color}/e$
and perform the same series of contraction bringing initially
$\mathcal{G}$. The end result is $\mathcal{G}/e$. 
Thus the equivalence class of $\mathcal{G}/e$ is the w-colored
graph that we seek.  

\qed




We henceforth restrict the rank of graphs to $D=3$ and 
aim at studying the universal invariant polynomial extending
BR polynomial for this new category of graphs. The extension for any $D$ should require
more work but could be almost inferred from the subsequent 
analysis. From now rank 3 w-colored graphs  will be
called more simply w-colored graphs. 

Mostly, we have studied non self-loop edges so far and their
main properties under contraction and cut 
can be guessed in any dimension. Self-loops are more subtle
and their behavior under contraction is much more involved.
Restricting to dimension 3 will simplify the analysis. 

Self-loops find also a meaning in the present situation. 
A self-loop can be at most a 3--inner edge.
A 3--inner edge determines by itself a graph, see Figure \ref{fig:mpinner}O.   
If it is a 2--inner self-loop then $e$ should be of the  
form illustrated in Figure \ref{fig:mpinner}A. Otherwise, $e$ may be a 
1--inner self-loop (Figure \ref{fig:mpinner}B) or a 0--inner 
(Figure \ref{fig:mpinner}C). 



\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=10cm, height=2.5cm]{wp-inner.pdf}
\vspace{0.4cm}
\caption{ {\small  $p$--inner self-loops: a 3--inner  (O)
and a 2--inner (A) self-loop with their unique possible configuration; a 1--inner self-loop with possible two sectors $v_1$ and $v_2$ (B) and a 0--inner self-loop with three  possible sectors $v_1,v_2$ and $v_3$ (C). }}
\label{fig:mpinner}
\end{minipage}
\put(-296,-19){O}
\put(-215,-19){A}
\put(-133,-19){B}
\put(-52,-19){C}
\put(-133,51){$v_1$}
\put(-133,-7){$v_2$}
\put(-52,51){$v_1$}
\put(-52,30){$v_2$}
\put(-52,-7){$v_3$}
\end{figure}

For a 2--inner self-loop $e$,  the outer strand of $e$ should be
in contact with other flags or edges, otherwise $e$ would be 
a 3--inner edge. We represent the rest of the vertex with 
possible edges and flags attached by a black diagram in Figure \ref{fig:mpinner}A. 

A 1--inner self-loop $e$ has two outer strands which should be 
in contact with two sectors of the vertex, $v_1$ and $v_2$ as illustrated in Figure \ref{fig:mpinner}B, such that $v_1$ and $v_2$ have at least 
two flags or edges. Remark that nothing prevents $v_1$ and $v_2$ to
have pre-flags in common or to be linked by bows. 
In this situation, we shall say that these sectors coincide
otherwise we call them separate.  
A 2--inner self-loop  $e$ has three such sectors, $v_1,v_2$ and $v_3$, which can pairwise coincide 
or can be pairwise separate. Separate sectors should
contain each  at least two flags or edges. 

The notion of trivial self-loop can be addressed at this point for this
category of graphs. We call a self-loop $e$ trivial if it is a 3--inner or 2--inner 
self-loop or if it is a 1--inner or 0--inner  self-loop 
such that there is no edge between separate sectors $v_i$.


For a 3--inner self-loop, the contraction gives three trivial 
discs, see Figure \ref{fig:wpcont}O. 
For a trivial 2--inner self-loop the contraction is still straightforward and yields 
Figure \ref{fig:wpcont}A. 
For a 1--inner self loop contraction (see Figure \ref{fig:wpcont}B), one gets one extra disc
 and has two possible configurations: either the vertex 
remains connected or it gets disconnected with two (possibly non trivial) vertices in both situations.  
Concerning the contraction of a trivial 1--inner self-loop, it is immediate that the vertex gets disconnected in two 
non trivial vertices.  
For a 0--inner self-loop contraction (see Figure \ref{fig:wpcont}C), we have no additional 
disc but three types of configurations with up to three 
disconnected (and possibly non trivial) vertices.
The contraction of a trivial 0--inner self-loop yields directly 
three disconnected and non trivial vertices. 

\begin{figure}[h]
 \centering
     \begin{minipage}[t]{.8\textwidth}
      \centering
\includegraphics[angle=0, width=9cm, height=1.5cm]{wp-cont.pdf}
\vspace{0.3cm}
\caption{ {\small $p$--inner self-loop contractions
corresponding to O, A, B and C of Figure \ref{fig:mpinner}, respectively. }}
\label{fig:wpcont}
\end{minipage}
\put(-283,-17){O}
\put(-211,-17){A}
\put(-132,-17){B}
\put(-60,-17){C}
\put(-144,45){$v_1$}
\put(-144,-5){$v_2$}
\put(-75,36){$v_1$}
\put(-45,36){$v_2$}
\put(-62,-5){$v_3$}
\end{figure}


\begin{lemma}[Rank 3 trivial self-loop contraction]
\label{lem:tris}
Let $\mathfrak{G}$ a w-colored graph and $\mathcal{G}$ any of its representative
with boundary $\partial{\mathcal{G}}$,
 $e$ be a trivial self-loop of $\mathcal{G}$, and $\mathcal{G}'=\mathcal{G}/e$
the result of the contraction of $\mathcal{G}$ by $e$ with boundary
denoted by $\partial{\mathcal{G}}'$. 
 Let $k$ denote the number of connected components
of $\mathcal{G}$, $V$ its number of vertices, $E$ its number of edges, $F_{{\rm int}}$ its number of faces, $B_{\rm int}$ its number of closed bubbles and $B_{\rm ext}$ its number of open bubbles, $C_\partial$ the number of connected component of $\partial{\mathcal{G}}$, $f=V_\partial$ its number of flags, $E_\partial=F_{{\rm ext}}$ the number of edges  and $F_\partial$
the number of faces of  $\partial{\mathcal{G}}$, and let $k',V',E',F_{{\rm int}},C'_\partial, B'_{{\rm int}},B'_{\rm ext}, C'_\partial,f', E'_\partial$, and $F'_\partial$ denote the similar numbers for $\mathcal{G}'$ and its boundary $\partial{\mathcal{G}}'$. 

$\bullet$ If $e$ is a 3--inner self-loop, then 
\begin{eqnarray}
&&
k' = k + 2\,, \quad 
V' = V+2  \,, \quad 
E' = E-1 \, , \quad 
F'_{{\rm int}} = F_{{\rm int}} \,,  \crcr
&&
C'_\partial= C_\partial \,, \quad
f' = f\,, \quad
E'_\partial = E_\partial\, ,
\quad  F'_{\partial } = F_{\partial }\,, \crcr
&& B'_{\rm int} = B_{{\rm int}} -3\,, \qquad 
B'_{\rm ext} =  B_{\rm ext}\,.
\label{eq:cself3}
 \end{eqnarray}
  

$\bullet$ If $e$ is a 2--inner self-loop, then 
\begin{eqnarray}
&&
k' = k + 2 \,, \quad 
V' = V+2  \,, \quad 
E' = E-1 \, , \quad 
F'_{{\rm int}} = F_{{\rm int}} \,, \crcr
&&
C'_\partial= C_\partial \,, \quad
f' = f\,, \quad 
E'_\partial = E_\partial \,, \quad
 F'_\partial = F_\partial \,, \crcr
&&
B'_{\rm int} = B_{{\rm int}} -1\,, \qquad 
B'_{\rm ext} =  B_{\rm ext}\,.
\label{eq:cself2}
 \end{eqnarray}


$\bullet$  If $e$ is a trivial $p$--inner self-loop such that $p=0,1$,
then 
\begin{eqnarray}
&&
k' = k + 2 \,, \quad 
V' = V+2  \,, \quad 
E' = E-1 \, , \quad 
F'_{{\rm int}} = F_{{\rm int}} \,, \crcr
&& 
C'_\partial= C_\partial \,, \quad
f' = f\,, \quad 
E'_\partial = E_\partial \,, \quad
 F'_\partial = F_\partial \,, \crcr
&& 
B'_{\rm int} + B'_{\rm ext} = B_{{\rm int}} + B_{\rm ext}  + \alpha_p \,,
\label{eq:cselfp}
 \end{eqnarray}
where $\alpha_{p} =3-2p$.

\end{lemma}
\proof 

$\bullet$ The first situation of a 3--inner self-loop  defines a particular
closed graph made of a single vertex with a unique self-loop. 
The contraction destroys the vertex and the three closed bubbles and generate three discs. 
The result follows. 


For $p$--inner self loops, $p\leq 2$, there should be other flags
or edges on the same end vertex. 
The first lines of \eqref{eq:cself2}-\eqref{eq:cselfp} should not cause any difficulty using the definition of the contraction which preserve (open
and closed) strands. 
Let us focus on the number of bubbles of the graph. 


$\bullet$ Consider that $e$ is 2--inner. One first should notice that there is a bubble generated by the two inner faces of $e$ and that contracting $e$ destroys this closed bubble. Besides, the other (open or closed) bubbles which passed through $e$ and which were defined by one of the two inner faces are simply deformed. They loose one face (the inner) but remain in the contracted graph. The second line of \eqref{eq:cself2} follows. 

 Let us assume now that $e$ is trivial and 1-- or 0--inner with color $a$. 
Consider in the initial  vertex $v$, the two or three separate sectors of pre-flags $v_1$, $v_2$ and $v_3$ determined by the strands of $e$.  
We remind that $v_1$, $v_2$ and $v_3$ should contain each at least two flags or edges. Consider as well the three 
bubbles labeled by colors $(aa_1a_2)$, $(aa_1a_3)$ and $(aa_2a_3)$ 
passing through $e$. 

$\bullet$ If $e$ is 1--inner,  let us assume that the face $(aa_3)$ 
is the one which is inner, without loss of generality. The edge $e$ decomposes in three
ribbon edges each determined by a couple of pairs $(aa_i; aa_j)$, 
$i<j$, such that the strand $(aa_1)$ has an end point in the sector 
$v_1$ and $(aa_2)$ an end point in $v_2$. 
  If $e$ is trivial and 1--inner, its contraction yields two connected vertices
plus one disc. Note that only the bubbles $\bee_{aa_1a_3}$
and $\bee_{aa_2a_3}$ (in the whole graph) include the face $(aa_3)$.
Contracting $e$, the bubbles $\bee_{aa_1a_3}$
and $\bee_{aa_2a_3}$ just loose that face but are still
present since in $v_1$ and $v_2$, there exist still 
faces where $\bee_{aa_1a_3}$ and $\bee_{aa_2a_3}$ passed
before. Now the last bubble $\bee_{aa_1a_2}$ 
gets split in two parts: these parts are disjoint 
bubbles with the same triple colors since there is no
edge in the graph relating them. 
These bubbles can be open or
closed depending on the nature of $\bee_{aa_1a_3}$ 
in $v_1$ and $v_2$. Hence, $B'_{{\rm int}} + B'_{\rm ext} = B_{{\rm int}} + B_{\rm ext}+1$.

$\bullet$ Now let us discuss the 0--inner self-loop situation
with its three separate sectors $v_1$, $v_2$ and $v_3$. The discussion
is somehow similar to the 1--inner case. 
The contraction of $e$ yields three connected vertices.
Using the similar routine explained above, one finds that
each of the bubbles $\bee_{aa_ia_j}$, $i<j$ gets split into 
two parts after the contraction. Each of these pairs of parts 
are not related at all by any edge or bow. Thus each bubble 
produces two bubbles. The resulting bubbles  
may be open or closed depending on the nature of $\bee_{aa_ia_j}$
in each sector. 
We have $B'_{{\rm int}} + B'_{\rm ext} = B_{{\rm int}} + B_{\rm ext}+3$.

\qed

 It is clear that the contraction of a 2--inner self-loop 
also obeys \eqref{eq:cselfp} as well for $p=2$. In fact \eqref{eq:cself2} is a stronger result because it mainly separates the variation of the numbers
of closed and open bubbles.  For a general 1--inner self-loop contraction, 
it turns out that the number $B_{\rm int} + B_{\rm ext}$ may vary 
of 1 or not. Similarly, for a non necessarily trivial 0--inner self-loop contraction, the same number of bubbles may vary from 0,1,2 up to 3. 


\begin{lemma}[Faces of a bridge]\label{lem:str}
$\bullet$ The faces passing through a bridge of any representative of a rank 3 w-colored graph are necessarily open. 
$\bullet$ These faces belong to the same connected component
of the boundary graph of the representative.
\end{lemma}
\proof A bridge $e$ with color $a$ has three strands of color pairs $(aa_1)$, $(aa_2)$  and $(aa_3)$ defining three faces passing through 
$e$. 

The first point is quite clear: following a strand inside the graph,  for instance, on the left side of the bridge, before closing
that face one has to go on the other side of the bridge
without passing by $e$ (we recall that by the presence of strands with different color pair, we cannot pass twice by a bridge). This is impossible by definition of a bridge. 
Hence each strand should terminate inside of each side of the bridge
hence are open. 

Assume that one the faces, say $(aa_1)$, does not belong
to the same connected component of the boundary of the others.
Consider in its own connected component all 
boundary vertices.  Each of these vertices are of valence 3
equipped with edges with different color pairs $(a_i a_j)$. Since $(aa_1)$ 
should connect one of these boundary vertices, there exists
at least one vertex with half edges of color $a$ or $a_1$. Consider 
all possible vertices where the strand $(aa_1)$ could connect.  
There are $N_a$ and $N_{a_1}$ such vertices
whereas there are $N_{a_2}$ and $N_{a_3}$ vertices
which cannot be joined by $(aa_1)$.
Each of these vertices have $N_{a_\alpha}$, $\alpha=\emptyset,1,2,3$,
half edges of each color pair $(a_\alpha a_j)$, $j\neq \alpha$. 
Since all these half-edges should be fully paired 
in order to have a connected component therefore each of the
following sums should give an even positive integer 
\begin{eqnarray}
N_a + N_{a_1}  + 1\,, \qquad 
N_a + N_{a_j}\,,    \qquad
N_{a_1} + N_{a_j}\,, \quad j=2,3\,.
\end{eqnarray}
This system is clearly inconsistent.

\qed

\begin{lemma}[Cut/contraction of special edges]\label{lem:cutbri}
Let $\mathcal{G}$ be a representative of $\mathfrak{G}$ a rank 3 w-colored graph
and $e$ an edge in $\mathcal{G}$. Then, 

$\bullet$ if $e$ is a bridge,  
in the above notations, we have 
\begin{eqnarray}
&&
k(\mathcal{G}\vee e) = k(\mathcal{G}/e)+1 ,\;
V(\mathcal{G}\vee e) = V(\mathcal{G}/e) + 1 ,\;
E(\mathcal{G}\vee e) = E(\mathcal{G}/e),\;
f(\mathcal{G} \vee e)= f(\mathcal{G}/e) +2, \crcr
&& \label{eq:kve} \\
&&
F_{{\rm int}}(\mathcal{G}\vee e)=  F_{{\rm int}}(\mathcal{G}/e) \,, \quad
B_{{\rm int}}(\mathcal{G} \vee e)=B_{{\rm int}}(\mathcal{G}/e)  \,,
\label{eq:fint} \\
&&  
C_\partial(\mathcal{G} \vee e) = C_\partial(\mathcal{G}/e)  +1\,,
\quad 
E_\partial(\mathcal{G} \vee e) = E_\partial (\mathcal{G}/e) +3 
\,, \quad
F_\partial(\mathcal{G} \vee e) = F_\partial(\mathcal{G}/e) + 3 \,,
\label{eq:cextbord} \\
&&
 B_{{\rm ext}}(\mathcal{G}\vee e) = B_{{\rm ext}}(\mathcal{G}/e) + 3\,;
\label{eq:bubext} 
\end{eqnarray}

$\bullet$ if $e$ is a trivial $p$--inner self-loop, $p=0,1,2$, we have  
\begin{eqnarray}
&&
k(\mathcal{G}\vee e) = k(\mathcal{G}/e)-2 ,\;
V(\mathcal{G}\vee e) = V(\mathcal{G}/e)- 2 ,\;
E(\mathcal{G}\vee e) = E(\mathcal{G}/e),\;
f(\mathcal{G} \vee e)= f(\mathcal{G}/e) +2, \crcr
&& \label{eq:kvep} \\
&&
F_{{\rm int}}(\mathcal{G}\vee e)+ C_\partial(\mathcal{G} \vee e) 
=  F_{{\rm int}}(\mathcal{G}/e) + C_\partial(\mathcal{G}/e)-2\,, 
\quad 
 E_\partial(\mathcal{G} \vee e) = E_\partial (\mathcal{G}/e) + 3\,,
\label{eq:fintp} \\
&&
B_{{\rm int}}(\mathcal{G} \vee e) +  B_{{\rm ext}}(\mathcal{G}\vee e) 
=B_{{\rm int}}(\mathcal{G}/e)  + B_{{\rm ext}}(\mathcal{G}/e) - (3-2p)\,.
\label{eq:cextp} 
\end{eqnarray}
 Moreover, given $\partial \mathcal{G}$ the boundary of $\mathcal{G}$ and
 a bridge or trivial $p$--inner self-loop $e$,  $p=0,1,2,3$,
\begin{equation}
2C_\partial(\mathcal{G} \vee e) - \chi(\partial(\mathcal{G} \vee e)) =
2C_\partial(\mathcal{G}) -  \chi(\mathcal{G}) = 2C_\partial(\mathcal{G}/e) -  \chi(\partial(\mathcal{G}/e)) \,,
\label{eq:chi} 
\end{equation}
where $\chi(\partial{\mathcal{G}})$ denote the Euler characteristics of the boundary of $\mathcal{G}$. 


 \end{lemma}
\proof We start by the bridge case. 
The equations in \eqref{eq:kve} are easily found. 
Let us focus on \eqref{eq:fint}. By Lemma \ref{lem:str}, 
we know that necessarily the faces passing through $e$ are open. 
All closed faces on each side of the bridge are conserved
after cutting $e$. The same are still conserved after
edge contraction. Hence $F_{{\rm int}}(\mathcal{G}\vee e) = F_{{\rm int}}(\mathcal{G}/e)$
and $B_{{\rm int}}(\mathcal{G} \vee e)=B_{{\rm int}}(\mathcal{G}/e)$. 
We now prove \eqref{eq:cextbord}. Still by the second point of 
Lemma \ref{lem:str}, the three external faces belong to the same 
boundary component. After cutting $e$, this unique component
yields two  boundary components.  It is direct to get 
$C_\partial(\mathcal{G} \vee e) = C_\partial(\mathcal{G}/e)  +1$,
$E_\partial(\mathcal{G} \vee e)= E_\partial (\mathcal{G}/e)+3$
(the cut of $e$ divides each external face into two different 
external strands) and 
$F_\partial(\mathcal{G} \vee e)= F_\partial (\mathcal{G}/e)+3$
because $C_\partial(\mathcal{G}/e)=C_\partial(\mathcal{G})$,
$E_\partial (\mathcal{G}/e)=E_\partial (\mathcal{G})$
and $F_\partial(\mathcal{G} /e)= F_\partial (\mathcal{G})$
 which are immediate from Lemma \ref{lem:fullcont}.
Concerning the number of external bubbles,
there are three bubbles in $\mathcal{G}$ passing through the 
bridge. Each of these is associated with 
two color pairs $(aa_i;aa_j)$, $i<j$. These bubbles
are clearly in $\mathcal{G}/e$ and cutting the bridge 
each of these bubble splits in two. This yields \eqref{eq:bubext}. 

We focus now on a trivial $p$--inner self-loop $e$. 
The relations \eqref{eq:kvep} can be determined without difficulty. 
We concentrate on the rest of the equations. 
Consider the faces $f_i$ in $e$ made with outer strands.
For $p=0,1,2$,  we have $f_{i}$, $1\leq i\leq 3-p$. These 
faces can be open or closed. We do a case by case study
according to the number of open or closed faces among the
$f_i$'s. 

- Assume that $3-p$ of $f_i$'s are closed.
Cutting $e$ entails 
\begin{eqnarray}
&&
F_{{\rm int}}(\mathcal{G}\vee e) = F_{{\rm int}} (\mathcal{G}) -3
\,,\quad 
C_{\partial}(\mathcal{G} \vee e) = C_\partial (\mathcal{G}) +1
\, , \quad
 E_\partial(\mathcal{G} \vee e) = E_\partial(\mathcal{G}) +3 \,,\crcr
&&
B_{{\rm int}}(\mathcal{G} \vee e)  + B_{{\rm ext}}(\mathcal{G} \vee e) 
 = B_{{\rm int}}(\mathcal{G})  + B_{{\rm ext}}(\mathcal{G}) \,,
\label{eq:f3} \\
&& 
 F_\partial(\mathcal{G} \vee e) = F_\partial(\mathcal{G}) + 3 \,.
\label{eq:fpa3} 
\end{eqnarray}
Note that in this situation only the variation of the total number of bubbles can be known.

- Assume that $3-p-1$ of the $f_i$'s are closed
and one is open. Cutting $e$ gives 
\begin{eqnarray}
&&
F_{{\rm int}}(\mathcal{G}\vee e) = F_{{\rm int}} (\mathcal{G}) -2
\,,\quad 
C_{\partial}(\mathcal{G} \vee e) = C_\partial (\mathcal{G}) 
\, , \quad 
 E_\partial(\mathcal{G} \vee e) = E_\partial(\mathcal{G}) +3\,,\crcr
&&
B_{{\rm int}}(\mathcal{G} \vee e)  = B_{{\rm int}}(\mathcal{G})  -1\,,
\quad 
 B_{{\rm ext}}(\mathcal{G} \vee e)  = B_{{\rm ext}}(\mathcal{G})  + 1\,,
\label{eq:f31}
\\
&&
 F_\partial(\mathcal{G} \vee e) = F_\partial(\mathcal{G}) +1 \,.
\label{eq:fpa31}
\end{eqnarray}

- Assume that $3-p-2$ of the $f_i$'s are closed
and two are open. Cutting $e$ gives 
\begin{eqnarray}
&&
F_{{\rm int}}(\mathcal{G}\vee e) = F_{{\rm int}} (\mathcal{G}) -1
\,,\quad 
C_{\partial}(\mathcal{G} \vee e) = C_\partial (\mathcal{G}) -1
\, ,\quad
 E_\partial(\mathcal{G} \vee e) = E_\partial(\mathcal{G}) +3\,,\crcr
&&
B_{{\rm int}}(\mathcal{G} \vee e)  = B_{{\rm int}}(\mathcal{G})  \,,
\quad 
 B_{{\rm ext}}(\mathcal{G} \vee e)  = B_{{\rm ext}}(\mathcal{G})  \,,\label{eq:f32}\\
&&
 F_\partial(\mathcal{G} \vee e) = F_\partial(\mathcal{G})- 1\,.
\label{eq:fpa32}
\end{eqnarray}
Note that this case does not apply for $p=2$. 


- For $p=0$ an additional situation applies:  assume that all 
 three $f_i$'s are open. Cutting $e$ gives 
\begin{eqnarray}
&&
F_{{\rm int}}(\mathcal{G}\vee e) = F_{{\rm int}} (\mathcal{G}) 
\,,\quad 
C_{\partial}(\mathcal{G} \vee e) = C_\partial (\mathcal{G}) -2
\, ,\quad
 E_\partial(\mathcal{G} \vee e) = E_\partial(\mathcal{G}) +3\,,\crcr
&&
B_{{\rm int}}(\mathcal{G} \vee e)  = B_{{\rm int}}(\mathcal{G})  \,,
\quad 
 B_{{\rm ext}}(\mathcal{G} \vee e)  = B_{{\rm ext}}(\mathcal{G})  \,,\label{eq:f33}\\
&&
 F_\partial(\mathcal{G} \vee e) = F_\partial(\mathcal{G})- 3\,.
\label{eq:fpa33}
\end{eqnarray}
Lemma \ref{lem:tris} relates  the same numbers for $\mathcal{G}/e$ and $\mathcal{G}$ from which one is able to prove \eqref{eq:fintp} and \eqref{eq:cextp}. 

 
Last, we prove the relation \eqref{eq:chi} on the Euler characteristics 
of the different boundaries. We first note that, from \eqref{eq:kve}, \eqref{eq:cextbord}, \eqref{eq:kvep} and  \eqref{eq:fintp}, for any special (bridge or trivial $p$--inner, $p=0,1,2$) edge,  
\begin{equation}
f(\mathcal{G} \vee e) = f(\mathcal{G})+ 2 = f(\mathcal{G}/e) + 2\,, \qquad 
E_\partial (\mathcal{G} \vee e) =E_\partial(\mathcal{G}) +3 = E_\partial(\mathcal{G}/e) +3 \,.
\label{eq:fe}
\end{equation}
For the bridge case, \eqref{eq:chi} follows from the relations
$F_\partial (\mathcal{G} \vee e) =  F_\partial(\mathcal{G}) +3 = F_\partial(\mathcal{G}/e) +3$ 
and $C_\partial (\mathcal{G} \vee e) = C_\partial(\mathcal{G}) +1= C_\partial(\mathcal{G}/e) +1$ 
in \eqref{eq:cextbord}. The result holds also for trivial $0,1,2$--inner self-loops, after the case by case study giving \eqref{eq:f3}--\eqref{eq:fpa33}.
Last, for the 3--inner self-loop, in addition to \eqref{eq:fe} which still holds, the following relations are valid
\begin{eqnarray}
C_\partial(\mathcal{G} \vee e) = C_\partial(\mathcal{G})+1 = C_\partial(\mathcal{G}/e)+1\,,
\quad 
F_\partial (\mathcal{G} \vee e) =F_\partial(\mathcal{G}) +3 = F_\partial(\mathcal{G}/e) +3 \,,
\end{eqnarray}
and allow us to conclude. 

 
\qed

\pagebreak


\subsection{Polynomial invariant for $3D$ w-colored tensor graphs}
\label{subset:polymt}

We shall define first an invariant for rank 3 w-colored graphs,
check its consistency and then state our main result. 

\begin{definition}[Topological invariant for rank 3 w-colored 
graph]\label{def:topotens}

Let $\mathfrak{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^0)$ be a rank 3 w-colored stranded graph with flags. 
The generalized topological invariant associated with $\mathfrak{G}$
is given by the following  function associated with any of its 
representatives $\mathcal{G}$ (using the above notations)
\begin{eqnarray}
&&
\mathfrak{T}_{\mathfrak{G}}(x,y,z,s,w,q,t) =\mathfrak{T}_{\mathcal{G};a}(x,y,z,s,w,q,t)= \label{ttopfla}\\
 && \sum_{A \Subset \mathcal{G}}
 (x-1)^{{\rm r}\,(\mathcal{G})-{\rm r}\,(A)}(y-1)^{n(A)}
z^{5k(A)-[3(V- E(A))+2(F_{{\rm int}}(A)-B_{{\rm int}}(A)-B_{{\rm ext}}(A))]} \crcr
&& \qquad \times \quad  s^{C_\partial(A)} \,  w^{F_{\partial}(A)} q^{E_{\partial}(A)} t^{f(A)}\,.
\nonumber
\end{eqnarray}
\end{definition}

Our initial task is to show that the above definition does not
actually depend on the representative $\mathcal{G}$ of $\mathfrak{G}$. 
Given any other representative $\mathcal{G}'$ of $\mathfrak{G}$, 
there is a one to one map between spanning c-subgraphs
of $\mathcal{G}$ and those of $\mathcal{G}'$. This can be achieved by 
 mapping any $A \Subset \mathcal{G}$ onto  $A' \Subset \mathcal{G}'$
such that $A' = (A\setminus D_{\mathcal{G}}) \cup D_{\mathcal{G}'}$ which can be easily 
inverted. Now, one checks that 
${\rm r}\,(\mathcal{G})$, ${\rm r}\,(A)$, $n(A)$ and $5k(A)-(3V+2F_{\rm int}(A))$ 
do not depend of the representative. The remaining 
exponents  $B_{\rm int}(A)$, $B_{\rm ext}(A)$, $C_\partial (A)$,
$f(A)$, $E_\partial(A)$ and $F_\partial(A)$ depend only on $A\setminus D_{\mathcal{G}} = A'\setminus D_{\mathcal{G}'}$ 
hence do not depend on the representative. 

One notices that the above consistency checking
 establishes that only the class of the spanning c-subgraphs
of some representative matters in the definition of $\mathfrak{T}_{\mathfrak{G}}$.  
Thus, we could have introduced a state sum on $\mathfrak{g} \Subset \mathfrak{G}$
in order to define this invariant directly from the equivalent classes
point of view using Proposition \ref{prop:classc}. 
We will keep however the more explicit formulation in terms of the
spanning  c-subgraphs of  representatives.


 
Another crucial point is to show that the exponent of $z$ 
in \eqref{ttopfla} is always a non negative integer. 

\begin{proposition}
\label{prop:euler}
Let $\mathcal{G}$ be any representative of $\mathfrak{G}$ a rank 3 w-colored 
graph. Then 
\begin{equation}
\zeta(\mathcal{G})= 3(E(\mathcal{G})- V(\mathcal{G})) + 2[ B_{{\rm int}}(\mathcal{G}) + B_{{\rm ext}}(\mathcal{G}) -F_{{\rm int}}(\mathcal{G}) ] \geq 0\,.
\end{equation}
\end{proposition}
\proof 
Let us consider the set of closed and  open bubbles 
$\mathcal{B}_{{\rm int}}$ and $\mathcal{B}_{{\rm ext}}$ of $\mathcal{G}$, respectively
(in this proof, we drop the dependence in the graph $\mathcal{G}$ in all
quantities). 
Let $B_{{\rm int}}$ and $B_{{\rm ext}}$ be their respective cardinal. 
Each open or closed bubble $\bee$ is an open or
a closed ribbon graph with $V_{\bee}$ number of vertices,
$E_{\bee}$ number of edges, $F_{{\rm int}; \bee}$ number
of closed faces and $C_{\partial}(\bee)$ number of closed faces
obtained uniquely from open strands after pinching (coinciding with the
number of connected component of the boundary of the open bubble $\bee$). 

Any $\bee_i \in \mathcal{B}_{{\rm int}}$ being a closed ribbon graph,  its Euler characteristics writes
\begin{equation}
 2- \kappa_{\bee_i} = V_{\bee_i} - E_{\bee_i} + F_{{\rm int}; \bee_i}\,,
\end{equation}
where $\kappa_{\bee_i}$ refers to the genus of $\bee_i$ or twice its genus 
if $\bee_i$ is oriented. Summing over all internal bubbles, we get
\begin{equation}
2 B_{{\rm int}} - \sum_{\bee_i \in \mathcal{B}_{{\rm int}}} \kappa_{\bee_i}
  = \sum_{\bee_i \in \mathcal{B}_{{\rm int}}}\left[ V_{\bee_i} - E_{\bee_i} + F_{{\rm int}; \bee_i}\right] .
\label{eq:euli}
\end{equation}
Using the colors, one observes that 
each edge of $\mathcal{G}$ splits into three ribbon edges belonging either
to an open or a closed bubble, and each internal face of $\mathcal{G}$ belongs to  two bubbles which might be open or closed. Thus we have
\begin{equation}
\sum_{\bee_i \in \mathcal{B}_{{\rm int}}} E_{\bee_i} + \sum_{\bee_x
\in \mathcal{B}_{{\rm ext}}} E_{\bee_x}  = 3E\, , \qquad
\sum_{\bee_i \in \mathcal{B}_{{\rm int}}} F_{{\rm int};\bee_i} + \sum_{\bee_x
\in \mathcal{B}_{{\rm ext}}} F_{{\rm int};\bee_x}  = 2F_{{\rm int}}\,.
\label{eq:efi}
\end{equation}
In addition, each vertex of the graph can be decomposed,
at least, in three vertices (3 vertices is the minimum given by 
the simplest vertex of the form $\mathcal{G}_1$ in Figure \ref{fig:npb}) which could belong to an open or closed bubble, we have
\begin{equation}
\sum_{\bee_i \in \mathcal{B}_{{\rm int}}} V_{\bee_i} + \sum_{\bee_x
\in \mathcal{B}_{{\rm ext}}} V_{\bee_x}  \geq  3V\,.
\label{eq:veri}
\end{equation}
Combining \eqref{eq:efi} and \eqref{eq:veri}, we re-write \eqref{eq:euli} as
\begin{equation}
3V - 3E +2F_{{\rm int}} - 2B_{{\rm int}} -
\sum_{\bee_x \in \mathcal{B}_{{\rm ext}}}\left[ V_{\bee_x} - E_{\bee_x} + F_{{\rm int}; \bee_x}\right] \leq   - \sum_{\bee_i \in \mathcal{B}_{{\rm int}}} \kappa_{\bee_i} \,.
\label{eq:pres}
\end{equation}
We complete the last sum involving $\mathcal{B}_{{\rm ext}}$ by adding
$C_{\partial}(\bee_x)$ in order to get
\begin{eqnarray}
\sum_{\bee_x \in \mathcal{B}_{{\rm ext}}}\left[ V_{\bee_x} - E_{\bee_x} + F_{{\rm int}; \bee_x} + C_{\partial}(\bee_x)\right] = 
\sum_{\bee_x \in \mathcal{B}_{{\rm ext}}} (2 - \kappa_{\widetilde\bee_x})\,,
\end{eqnarray}
which, substituted in \eqref{eq:pres}, leads us to
\begin{eqnarray}
3V - 3E +2F_{{\rm int}} - 2B_{{\rm int}} - 2B_{{\rm ext}} 
 \leq   - \sum_{\bee_i \in \mathcal{B}_{{\rm int}}} \kappa_{\bee_i} 
- \sum_{\bee_x \in \mathcal{B}_{{\rm ext}}} \big( C_{\partial}(\bee_x) + \kappa_{\widetilde\bee_x}\big) 
\label{eq:pres2}
\end{eqnarray}
from which the lemma results. 
\qed

\vspace{0.4cm}

In fact, $ \sum_{\bee_x \in \mathcal{B}_{{\rm ext}}} C_{\partial}(\bee_x)= F_\partial(\mathcal{G})$ is the number of faces of the boundary graph
$\mathcal{G}$ (see Remark \ref{rem:1}). The above bound can be refined since
$
F_\partial(\mathcal{G}) \geq B_{{\rm ext}}(\mathcal{G})
$
which merely follows from the fact that each $\bee_x \in \mathcal{B}_{{\rm ext}}$
has at least a boundary contributing to $F_\partial(\mathcal{G})$
such that 
\begin{eqnarray}
B_{{\rm ext}}(\mathcal{G}) \leq \sum_{\bee_x} C_{\partial}(\bee_x) = F_{\partial}(\mathcal{G})\,.
\end{eqnarray}
Thus we also have 
\begin{equation}
3V - 3E +2F_{{\rm int}} - 2B_{{\rm int}} - B_{{\rm ext}} 
 \leq   - \sum_{\bee_i \in \mathcal{B}_{{\rm int}}} \kappa_{\bee_i} 
- \sum_{\bee_x \in \mathcal{B}_{{\rm ext}}} \kappa_{\widetilde\bee_x}\,.
\end{equation}
This may lead as well to yet another well defined invariant.
However, we will not use this relation in the following
due to some rich relations that  $-\zeta(A) \geq 0$
entails. In particular, we have other  positive combinations.

\begin{proposition}\label{prop:14}
Let $\mathcal{G}$ be any representative of $\mathfrak{G}$ a rank 3 w-colored 
graph. Then 
\begin{eqnarray}
&&
\zeta'(\mathcal{G})= 3[E(\mathcal{G})- V(\mathcal{G})] + 2[ B_{{\rm int}}(\mathcal{G}) + B_{{\rm ext}}(\mathcal{G}) -F_{{\rm int}}(\mathcal{G}) -C_\partial(\mathcal{G})] \geq 0\,,\crcr
&&
\zeta''(\mathcal{G})= 3[E(\mathcal{G})- V(\mathcal{G})-C_\partial(\mathcal{G})] + 2[ B_{{\rm int}}(\mathcal{G}) + B_{{\rm ext}}(\mathcal{G}) -F_{{\rm int}}(\mathcal{G})] \geq 0\,.
\end{eqnarray}
\end{proposition} 
\proof By the color prescription, each connected component of the boundary of $\mathcal{G}$ has at least three faces. Therefore
\begin{eqnarray}
3 C_\partial \leq F_\partial \,. 
\end{eqnarray}
Then we also have $-F_\partial +2C_\partial \leq 0$. The proposition follows from \eqref{eq:pres2} and the fact that $F_\partial = \sum_{\bee_x} C_{\partial}(\bee_x) $ in the proof of Proposition \ref{prop:euler}.

\qed 




Proposition \ref{prop:euler} ensures 
$\zeta(A)\geq 0$, for any $A \Subset \mathcal{G}$, hence the following
statement. 

\begin{proposition}[Polynomial invariant]
$\mathfrak{T}_{\mathfrak{G}}=\mathfrak{T}_{\mathcal{G}}$ is a polynomial. 
\end{proposition}

The quantity $V - E(A) + F_{{\rm int}}(A) - B_{{\rm int}}(A)$ 
is nothing but the Euler characteristics 
for a closed colored graph $A$ understood as a cellular complex \cite{Gurau:2009tw}. This quantity always proves to be  
bounded by $-\sum_{\bee_i} \kappa_{\bee_i}$.  
If the graph is not closed, the same cellular
complex has a boundary bearing itself a cellular decomposition. 
The quantity $-\zeta(A)$ represents, in the present specific 
instance, a weighted notion for Euler characteristics of the cellular complex corresponding to $A$ which also take into account the boundary due to $B_{{\rm ext}}$. The quantity $5k(A)-\zeta(A)$ will be however
the one of interest in the following. 

Let us call $\mathcal{G}^0$ a representative graph made only with a finite family of vertices with flags and without any edges possibly with discs. Then $E(\mathcal{G}^0)= B_{{\rm int}}(\mathcal{G}^0)=0$, $F_{{\rm int}}(\mathcal{G}^0)=D$, 
$D$ being the number of trivial discs in $\mathcal{G}^0$, $k(\mathcal{G}^0)= V(\mathcal{G}^0)$, 
$k(\mathcal{G}^0)-D=C_{\partial}(\mathcal{G}^0)\geq 0$, we can check the consistency of \eqref{ttopfla} as the following makes still a sense:
 \begin{equation}
\label{eq:bounmt}
\mathfrak{T}_{\mathcal{G}^0}(x,y,z,s,w,q,t)= 
z^{2[k(\mathcal{G}^0)-D+B_{{\rm ext}}(\mathcal{G}^0)]} 
s^{k(\mathcal{G}^0) - D}  w^{F_\partial(\mathcal{G}^0)} q^{E_\partial(\mathcal{G}^0)}\,t^{|\mathfrak{f}^0(\mathcal{G}^0)|}. 
\end{equation} 

It may exist several possible reductions of the above 
polynomial. We will however focus on the most 
prominent ones  given by 
\begin{eqnarray}
&&
\mathfrak{T}_{\mathcal{G}} (x,y,z,z^{-2},w,q,t) = \mathfrak{T}'_{\mathcal{G}} (x,y,z,w,q,t)  \,,
\quad \mathfrak{T}_{\mathcal{G}} (x,y,z,z^{-2}s^{2},s^{-1},s,s^{-1}) = \mathfrak{T}''_{\mathcal{G}} (x,y,z,s)\,, \label{eq:mtprim} \crcr
&&
\mathfrak{T}_{\mathcal{G}} (x,y,z,z^{2}z^{-2},z^{-1},z,z^{-1}) = \mathfrak{T}'''_{\mathcal{G}} (x,y,z) \,. \crcr
&&
\end{eqnarray}
Proposition \ref{prop:14} ensures that $\mathfrak{T}'_{\mathcal{G}}$
is a polynomial. Meanwhile, $\mathfrak{T}''_{\mathcal{G}}$ is also a polynomial
with exponent of $s$ the Euler characteristics of the boundary $\partial{\mathcal{G}}$.
$\mathfrak{T}'''_{\mathcal{G}} (x,y,z) $ combine both invariants in a single exponent. These polynomials will be relevant in the next analysis.  
Note that we could have introduced another polynomial
between $\mathfrak{T}'$ and $\mathfrak{T}''$ which expresses as 
$\mathfrak{T}_{\mathcal{G}} (x,y,z,s^{2},s^{-1},s,s^{-1}) = \mathfrak{T}^0_{\mathcal{G}} (x,y,z,s)$.
But this latter turns out to satisfy the same properties as 
$\mathfrak{T}$ and thus does not provide anything new.  


We are now in position to prove our main theorem. 

\begin{theorem}[Contraction/cut rule for w-colored graphs]
\label{theo:contens}
Let $\mathfrak{G}$ be a rank 3 w-colored graph with flags. Then, for a regular edge $e$ of any of the representative $\mathcal{G}$ of $\mathfrak{G}$, we have
\begin{equation}
\mathfrak{T}_{\mathcal{G}}=\mathfrak{T}_{ \mathcal{G}\vee e} +\mathfrak{T}_{\mathcal{G}/e}\,,
\label{tenscondel}
\end{equation} 
for a bridge $e$, we have $\mathfrak{T}_{\mathcal{G} \vee e}= z^8s(wq)^3t^2 \mathfrak{T}_{\mathcal{G}/e}$
and 
\begin{equation}
\mathfrak{T}_{\mathcal{G}} =[(x-1)z^8s(wq)^3t^2+1] \mathfrak{T}_{\mathcal{G}/e}\,;
\label{tensbri}
\end{equation} 
 for a trivial p-inner self-loop $e$, $p=0,1,2$, we have 
\begin{equation}
\mathfrak{T}_{\mathcal{G}}=\mathfrak{T}_{\mathcal{G} \vee e} + (y-1)z^{4p-7}\,\mathfrak{T}_{\mathcal{G}/e}\,.
\label{tensself}
\end{equation} 
\end{theorem}

\proof
Let  $\mathcal{G}$ be any representative of the class $\mathfrak{G}$. 
 Same  initial remarks as stated in the proof  
of Theorem \ref{theo:BRext} hold here for $\mathcal{G}$.  
Our main concern is the change in the number of internal 
and external bubbles and the independence of the final 
result on the representative $\mathcal{G}$. 

We concentrate first on \eqref{tenscondel}. 
 Consider an ordinary edge $e$ of $\mathcal{G}$, the set of spanning c-subgraphs which do not contain $e$ being the same  
as the set of spanning c-subgraphs of $\mathcal{G} \vee e$, 
 the number of open and closed bubbles on each subgraph is the same, 
it is direct to get $ \sum_{A \Subset \mathcal{G} ; e\notin A} (\cdot)=\mathfrak{T}_{\mathcal{G} \vee e} $.  Observe that the class of $\mathcal{G} \vee e$ defines $\mathfrak{G}\vee e$
from Lemma \ref{lem:cutmg} and we know that all exponents
in $\mathfrak{T}_{\tilde\mathcal{G}}$ do not depend on the representative $\tilde\mathcal{G}$ of the class of $\tilde\mathfrak{G}$. 
Hence $\mathfrak{T}_{\mathcal{G} \vee e} = \mathfrak{T}_{\mathfrak{G} \vee e} $ does not depend on the representative. 

Let us focus on the second term of \eqref{tenscondel}.
Consider $e$, its end vertices $v_1$ and $v_2$ and
 its 3 strands with color pairs $(aa_1)$, $(aa_2)$ 
and $(aa_3)$ and consider the set bubbles in $\mathfrak{G}$. 
Some bubbles do not use any strand of $e$  and three bubbles can be formed using these
strands (these are of colors $(aa_ia_j)$, $i<j$). Contracting now $e$, 
the vertex obtained is connected by Lemma \ref{lem:internal}.
The former  three strands $e$ are clearly preserved after the contraction.  
The bubbles not passing through $e$ are not affected at all 
by the procedure. The  three bubbles passing through $e$
are also preserved since  the contraction
do not delete faces or strands. The faces passing through $e$ getting 
only shortened,  the net result from the point of view of the bubbles 
passing through $e$ is simply an ordinary ribbon edge contraction in the sense of ribbon graphs. From this results
$\sum_{A \Subset \mathcal{G} ; e\in A} (\cdot)=\mathfrak{T}_{\mathcal{G} /e} $.
By Lemma  \ref{lem:cutmg}, we define $\mathfrak{G}/e$ 
and  conclude that the polynomial $\mathfrak{T}_{\mathfrak{G}/e}$
does not depend on the representative $\mathcal{G}/e$
of $\mathfrak{G}/e$. 
 

Let us focus now on the bridge case and \eqref{tensbri}. 
Cutting a bridge yields, as in the ordinary case, 
from the sum $\sum_{A \Subset \mathcal{G} ; e\notin A}$ the product
$(x-1)\mathfrak{T}_{\mathcal{G} \vee e}$. The second sum
remains as it is using the mapping between 
$\{A \Subset \mathcal{G};e\in A\}$ and $\{A\Subset \mathcal{G}/e\}$
and provided the fact that there is no change in the vertex contracted which is ensured by Lemma \ref{lem:internal}.  
The last stage relates $\mathfrak{T}_{\mathcal{G} \vee e}$ and $\mathfrak{T}_{\mathcal{G}/e}$. 
This can be achieved by using the bijection between $A\Subset \mathcal{G} \vee e$ and 
$A' \Subset \mathcal{G}/e$ where each $A$ and $A'$ are both 
uniquely related to some $A_0\Subset \mathcal{G}$ as $A = A_0\vee e$
and $A'=A_0/e$. Using Lemma \ref{lem:cutbri},
the relation \eqref{tensbri} follows. 
Then, Lemma  \ref{lem:cutmg} allows us to define ($\mathfrak{G}\vee e$
and) $\mathfrak{G}/e$ and to conclude that the resulting polynomials 
($\mathfrak{T}_{\mathcal{G} \vee e}$ and) $\mathfrak{T}_{\mathcal{G} /e}$ are independent on 
the representative ($\mathcal{G} \vee e$ and) $\mathcal{G}/e$. 

Next, we discuss the trivial $p$--inner self-loop case and prove \eqref{tensself}. 
The property that the sum $\sum_{A \Subset \mathcal{G} ; e\notin A}(\cdot) 
=\mathfrak{T}_{\mathcal{G} \vee e} $ should be direct. The second sum is now studied. 

The question is whether or not $e$
being a trivial $p$--inner self-loop in $\mathcal{G}$ remains as such in $A$.
The answer for that question is yes because $A$ contains the end vertex 
of $e$. We may cut some edges in each sectors $v_i$ (see Figure \ref{fig:mpinner}) for defining $A$ 
but the resulting sectors are still totally separated in $A$.  

Contracting a trivial $p$--inner self-loop generates $p$ discs 
and $3-p$ non trivial vertices. 
Now, from Lemma \ref{lem:tris}, we know how
evolve all numbers of components in the graph: the  nullity is again 
$n(A) = n(A') + 1$, and the exponent of $z$ becomes
\begin{eqnarray}
&&
5k(A) - (3(V(\mathcal{G}) - E(A)) + 2(F_{\rm int}(A) - B_{\rm int}(A)-B_{{\rm ext}}(A)) = \crcr
&&
5(k(A')-2) - \Big[3[V(\mathcal{G}/e)-2) - (E(A')+1)]
  + 2(F_{\rm int}(A') - B_{\rm int}(A')-B_{{\rm ext}}(A')+\alpha_p)\Big]\crcr
&&
 = 5k(A') - (3(V(\mathcal{G}/e) - E(A')) + 2(F_{\rm int}(A') - B_{\rm int}(A')-B_{{\rm ext}}(A')) 
 -7 +4p \,,
\label{eq:binter}
\end{eqnarray}
where $\alpha_p=3-2p$, $A$ and $A'$ refer to the subgraphs 
related by bijection between spanning c-subgraphs of $\{A \Subset \mathcal{G};e\in A\}$ and $\{A'\Subset \mathcal{G}/e\}$.  
At the end, one gets $(y-1)z^{4p-7}\mathfrak{T}_{\mathcal{G}/e}$. In the similar way as done before, we are able to conclude that this result is independent of the
representative. 

 \qed 



Some comments are in order at this point. 

- The existence of a function defined on $\mathfrak{G}$ 
satisfying the relations of Theorem \ref{theo:contens} 
is guaranteed by the explicit formula of $\mathfrak{T}_{\mathfrak{G}}$
given in Definition \ref{def:topotens}. The unicity of $\mathfrak{T}_{\mathfrak{G}}$
follows from its existence and can be 
only guaranteed by suitable ``boundary condition'' data
which are given by the bridge contraction \eqref{tensbri}
and the data of all one-vertex (rosette) w-colored graph
polynomials. These polynomials write again using the state sum (sum over subgraphs)  of such stranded rosette graphs \eqref{ttopfla}. 
These conditions  extend 
boundary conditions making unique the BR polynomial \cite{bollo}. 

- Note that in the equality \eqref{eq:binter} 
the number of bubbles  $B_{{\rm int}}+B_{{\rm ext}}$ plays a crucial role 
in the determination of  the  exponent of $z$. In addition, the contraction of 
a bridge for this category of graph with flags 
is close to the Tutte/BR relation for bridge contraction
since we do not need any constrain in 
the polynomial (for instance putting $s=z^{-1}$ in 
the case of the BR polynomial for graphs with flags) in order to obtain
a one term relation for such a terminal form.  
For the last contraction/cut for a trivial $p$--inner self-loop \eqref{tensself}, we
still cannot map $\mathfrak{T}_{\mathcal{G} \vee e}$ on $\mathfrak{T}_{\mathcal{G} /e}$. 
These features show that the polynomial
$\mathfrak{T}$ is a genuine extension of the BR polynomial.


\begin{corollary}[Cut/contraction relations for $\mathfrak{T}'$]
\label{coro:trpin}
Let $\mathfrak{G}$ be a rank 3 w-colored stranded graph with flags
and any of its representative $\mathcal{G}$.
Then,  for a bridge $e$,
we have $\mathfrak{T}'_{\mathcal{G} \vee e}= z^{6}(wq)^3t^2 \mathfrak{T}'_{\mathcal{G}/e}$ and
\begin{equation}
\mathfrak{T}'_{\mathcal{G}}(x,y,z,w,q,t) =[(x-1)z^6(qw)^3t^2+1] \mathfrak{T}'_{\mathcal{G}/e}(x,y,z,w,q,t)\,;
\label{eq:ctprimb}
\end{equation} 
for a trivial $p$--inner self-loop $e$ in $\mathcal{G}$, $0\leq p \leq 2$, 
we have
\begin{equation}
\mathfrak{T}'_{\mathcal{G}}(x,y,z,1,q,t)=z^{4p-6} [q^3t^2+ (y-1)z^{-1}]\,\mathfrak{T}'_{\mathcal{G}/e}(x,y,z,1,q,t)\,;
\label{tensselfp}
\end{equation} 

\end{corollary}

\proof Theorem \ref{theo:contens} implies naturally \eqref{eq:ctprimb}
 after the setting $s=z^{-2}$ in $\mathfrak{T}_{\mathcal{G}}$.  
We now work out the contraction/cut of the trivial self-loops. 

Same arguments as in the proof of Theorem \ref{theo:contens}
should be invoked here. The difference now is that 
by changing $s\to z^{-2}$, using (1) the one-to-one mapping 
between $\{A \Subset \mathcal{G}\vee e\}$ and $\{A' \Subset \mathcal{G}/e \}$
such that to each $A \Subset \mathcal{G}\vee e$ one associates 
$A' \Subset \mathcal{G}/e$ defined by $A'=\tilde A/e$,
$\tilde A\Subset \mathcal{G}$, and $\tilde A \vee e = A$
and (2) the relations 
\eqref{eq:kvep}-\eqref{eq:cextp} of  Lemma \ref{lem:cutbri},
we can map, for a trivial $0,1,2$--inner self-loop $e$,
$\mathfrak{T}_{\mathcal{G} \vee e}$ on $\mathfrak{T}_{\mathcal{G}/e}$. We compute the variation of the exponent of $z$ between $A$ and $A'$ as
\begin{eqnarray}
&&
5k(A) - (3(V(\mathcal{G}) - E(A)) + 2[F_{\rm int}(A) +C_\partial(A)- B_{\rm int}(A)- B_{{\rm ext}}(A)]) =\crcr
 &&
5(k(A')- 2 )- (3(V(\mathcal{G}')-2- 
E(A')) + 2[F_{\rm int}(A') +C_\partial(A')-2- 
B_{\rm int}(A') - B_{\rm ext}(A') + \alpha_p ])
\crcr
&& 
 = 5k(A') - (3(V(\mathcal{G}/e) - E(A')) + 2[F_{\rm int}(A') - B_{\rm int}(A') - B_{\rm ext}(A')])  -2\alpha_p \,.
\label{eq:bin}
\end{eqnarray}
The rest of the variations can be easily identified using the same
lemma. It can be proved that the result does not depend on the representative. 

\qed
\vspace{0.4cm} 

As a comment, for $w\neq 1$, $\mathfrak{T}'_{\mathcal{G} \vee e}$ cannot be fully 
mapped onto $\mathfrak{T}'_{\mathcal{G}/e}$ due to the fact that the number $F_\partial$  of face of the boundary of each subgraph cannot
be determined in that general situation. 
Nevertheless, we have two other noteworthy reductions which solve this issue without putting $w=1$. 




 \begin{corollary}[Cut/contraction rules for $\mathfrak{T}''$ (and $\mathfrak{T}'''$)]
\label{coro:trpin2}
Let $\mathfrak{G}$ be a rank 3 w-colored stranded graph with flags
and any of its representative $\mathcal{G}$.

Then, for a bridge $e$, we have $\mathfrak{T}''_{\mathcal{G} \vee e} = z^{6}\mathfrak{T}''_{\mathcal{G}/e}$
and 
\begin{equation}
\mathfrak{T}''_{\mathcal{G}} =[ (x-1)z^6 + 1]\,\mathfrak{T}''_{\mathcal{G}/e}\,;
\label{eq:cttrb}
\end{equation}
for a trivial $p$--inner self-loop $e$ in $\mathcal{G}$, $0\leq p \leq 2$, 
we have $\mathfrak{T}''_{\mathcal{G} \vee e} =z^{4p-6} \mathfrak{T}''_{\mathcal{G}/e}$ and 
\begin{equation}
\mathfrak{T}''_{\mathcal{G}}= z^{4p-6}[1+ (y-1)z^{-1}]\,\mathfrak{T}''_{\mathcal{G}/e}\,.
\label{eq:terself}
\end{equation} 
The same contraction and cut rules applies for $\mathfrak{T}'''_{\mathcal{G}}$. 
\end{corollary}
\proof The new ingredient to achieve the proof of this statement 
is \eqref{eq:chi} of Lemma \ref{lem:cutbri}. 

\qed


More remarks can be made at this stage.  

 - $\mathfrak{T}''$ and $\mathfrak{T}'''$ satisfy the same rules. Hence $\mathfrak{T}''$
which is more general becomes more relevant.  

 - We did not use the notion of product of graphs
for mapping the polynomials for $\mathcal{G} \vee e$ onto those of $\mathcal{G}/e$. 
In fact, even for ribbon graphs our approach applies. The dot product of graphs is however an elegant way to encode such a map. Certainly, this notion deserves
to be defined in the framework of stranded graphs
in order to achieve more calculations. For instance,
how the calculation of more involved graphs with many trivial 
self-loops can be inferred from the product of contributions
of much simpler trivial self-loops. 

- The exponents of  $z^{4p-7}$ or of $z^{4p-6}$ can be 
negative in some expressions.  This simply implies that
in the polynomial $\mathfrak{T}'_{\mathcal{G} /e}$ or $\mathfrak{T}''_{\mathcal{G} /e}$ all 
monomials should contain an enough large power of $z$
to render the overall expression a well defined polynomial. 

If  the notion of point graph multiplication of two disjoint graphs is not defined at this stage, in contrast, the disjoint union operation on graph extends
naturally in the present formulation.


\begin{lemma}[Disjoint union]\label{lem:disj}

Let $\mathfrak{G}_1$ and $\mathfrak{G}_2$ two disjoint rank 3 $w$-colored graphs, 
then 
\begin{equation}
\mathfrak{T}_{\mathfrak{G}_1 \sqcup \mathfrak{G}_2} = 
\mathfrak{T}_{\mathfrak{G}_1 } \, \mathfrak{T}_{\mathfrak{G}_2} \,.
\end{equation}
\end{lemma}
\proof This is totally standard as in the ordinary procedure
using additive properties of  exponents in $\mathfrak{T}_{\mathcal{G}}$. 

\qed 


\begin{corollary}[3--inner self-loop contraction]
\label{coro:term}
Given a rank 3 w-colored graph $\mathfrak{G}$ and $\mathcal{G}$
one of its representative containing a 3--inner self-loop $e$
then 
 \begin{equation}
\mathfrak{T}_{\mathcal{G}} = z^5(z^3s(wq)^3t^2 + y-1) \mathfrak{T}_{\mathcal{G}/e}\,.
\end{equation}
 \end{corollary}
\proof We use the fact that $e$ is a 3--inner then it forms
a separate subgraph $g$. In order to compute the polynomial
of $\mathcal{G}$, Lemma \ref{lem:disj} can be applied and a direct
evaluation of the graph $g$ yields the desired factor. 

\qed


\begin{definition}[Multivariate form]
The multivariate form associated with \eqref{ttopfla} is defined by:
 \begin{eqnarray}
&&
\widetilde\mathfrak{T}_{\mathfrak{G}}(x,\{\beta_e\},\{z_i\}_{i=1,2,3},s,w,q,t)= 
\widetilde\mathfrak{T}_{\mathcal{G}}(x,\{\beta_e\},\{z_i\}_{i=1,2,3},s,w,q,t) \label{tmulti}\\
&& =   \sum_{A \Subset \mathcal{G}}
 x^{{\rm r}\,(A)}(\prod_{e\in A}\beta_e)
z_1^{F_{{\rm int}}(A)}z_2^{B_{{\rm int}}(A)} z_3^{B_{{\rm ext}}(A)}\, 
s^{C_\partial(A)} \,  w^{F_{\partial}(A)} q^{E_{\partial}(A)} t^{f(A)}\,,
\nonumber
\end{eqnarray}
for $\{\beta_e\}_{e\in \mathcal{E}}$ labeling the edges of the graph $\mathcal{G}$. 
\end{definition}
It is direct to prove the following statement by ordinary techniques. 

\begin{proposition} For all regular edge $e$, 
\begin{eqnarray}
 \widetilde\mathfrak{T}_{\mathfrak{G}}=
\widetilde\mathfrak{T}_{ \mathfrak{G}\vee e} +x\beta_e\,\widetilde\mathfrak{T}_{\mathfrak{G}/e}\,.
\end{eqnarray}
\end{proposition}

\begin{remark}\label{rem:2}
We can now compare $\widetilde\mathfrak{T}$ with Gurau's  polynomial
denoted in the following by $G$ \cite{Gurau:2009tz}. We shall use however not the full form of $G_{\mathcal{G}}$ denoted $P_{\mathcal{G}}$  in \cite{Gurau:2009tz} but we will use instead two improvements: 
(1) the normalized form $P_{\mathcal{G}}(\{\beta_e x_1\},\dots)$ of $P_{\mathcal{G}}$,
where $x_1$ is the variable associated with the number of edges
which brings an inessential overall factor of $x_1^{E(A)}$
consistently absorbed by the $\beta_e$ 
and (2) a rank formulation of $G_{\mathcal{G}}(\{\beta_e\},\dots) =P_{\mathcal{G}}(\{\beta_e x_1\},\dots)$, i.e. rather then using two variables $x_0$ for the vertices
and $x_4$ for the number of connected components of the 
rank 3 colored tensor graph, we will simply use $x^{{\rm r}\,(A)}$, 
$A \Subset \mathcal{G}$. This notation is more compact and
${\rm r}\,(A)$ is the quantity depending only on the class of $A$.  

 
For a rank 3 colored tensor graph $\mathcal{G}$, the polynomials $\widetilde\mathfrak{T}$
and $G$ are related by 
\begin{equation}
\widetilde\mathfrak{T}_{\mathcal{G}}(x,\{\beta_e\}, z_1,z_2,z_3=1,s,w,q,t)
 = G_{\mathcal{G}}(x,\{\beta_e\},z_1,z_2,s,q,w,t)\,, 
\end{equation}
with, according to the convention in  \cite{Gurau:2009tz}, we have
\begin{eqnarray}
C_\partial = |\mathfrak{B}_{\partial}^3|, \quad 
F_\partial = |\mathfrak{B}_{\partial}^2|, \quad 
E_\partial = |\mathfrak{B}_{\partial}^1|, \quad 
f = |\mathfrak{B}_{\partial}^0|, \quad 
B_{{\rm int}}= |\mathfrak{B}^3|, \quad 
F_{{\rm int}} = |\mathfrak{B}^2|.
\end{eqnarray}
As expected, for this category of graphs the 
polynomial $\widetilde\mathfrak{T}$ is more general because it contains one additional variable (denoted above by $z_3$)
 which is associated with the number of external bubbles 
of the graph. This variable can be introduced
by hand in $G$ making it a little more general. This additional variable does not lead to any new features for the multivariate form
however, as seen in our developments, it plays an important role
in the non-multivariate form.  


\end{remark}
\vspace{0.4cm}

We finally wrap up this section with additional  insights: 
\vspace{0.1cm}


$\bullet$ We have successfully defined the classes of rank 3 w-colored stranded graphs  for which a natural contraction/cut rule makes a sense  and the associated polynomial invariants $\mathfrak{T}, \mathfrak{T}'$ and $\mathfrak{T}''$. 
Our results extend both BR polynomial to arbitrary 
contractions of colored tensor graphs of rank 3. 
The achievement of this requires to relax and to modify several initial concepts introduced by  Gurau (to mention a few, the meaning of 3-bubbles with now no fixed valence and the very notion 
of contraction itself, for instance).  The form of our polynomial 
is not primarily given in the multivariate form (as the one 
by Gurau). Thus, it has required a full-fledge proof in order 
to establish that  this polynomial is a genuine invariant for the present graphs.  
We have also successfully 
identified terminal forms of the contraction/cut sequence
for this type of graphs. Such a study of terminal forms 
has been never addressed in former works on stranded
graphs \cite{Gurau:2009tz}\cite{Tanasa:2010me}. 

$\bullet$ We stress that after the 
contraction of some $p$--inner self-loops, other 
remaining trivial $p'$--inner self-loops may 
change their number of $p'$ inner faces. 
This is the reason why given a certain number
of $m_p$  trivial $p$--inner self-loops, we cannot easily 
infer the number of trivial $0,1,2$-- or $3$--inner self-loops
which shall really contribute to the final evaluation of the
terminal form. In fact, we can show that contracting
a trivial $p$--inner self-loop at some point of the sequence
may only be neutral for or increase by 1 the number of inner faces of other $p$--inner self-loops. Hence, roughly speaking, after contraction
there may or may not have a ``migration'' of the elements of the set of $p$--inner self-loops to set of the $(p+1)$--inner self-loops, $p+1\leq 3$. 

In any case, the polynomial $\mathfrak{T}''$ of some terminal form $\mathcal{G}$ 
representative of a w-colored graph made only with  bridges and 
trivial $p$--inner self-loops can be computed as
 \begin{equation}
x^m \, \left[\prod_{p=0}^3\, \{z^{4p-6}[1+ (y-1)z^{-1}]\}^{n_p} \right] \times \mathfrak{T}''(\mathcal{G}^0)\,,
\label{eq:mpdbri}
\end{equation} 
for some integer $m,n_{0,1,2,3}$, and where $\mathfrak{T}''(\mathcal{G}^0)$ is the polynomial of $\mathcal{G}^0$ graph having only vertices and hence is given by \eqref{eq:bounmt}. After changing $s\to z^{-2}s^{2}$, one gets
\begin{equation}
\mathfrak{T}''(\mathcal{G}^0) = 
z^{2B_{{\rm ext}}(\mathcal{G}^0)}s^{2C_\partial(\mathcal{G}^0)
- (f(\mathcal{G}^0) - E_\partial(\mathcal{G}^0) + F_\partial(\mathcal{G}^0))}\,. 
\end{equation}
Note that the contribution \eqref{eq:mpdbri} only makes a sense as 
a polynomial if exponents $n_p$ are not arbitrary. 
One must have indeed
\begin{equation} 5n_3 +n_2 - 3n_1 - 7n_0 + 2B_{\rm ext}(\mathcal{G}^0)\geq 0\,,
\end{equation}
which should follow from Proposition \ref{prop:euler}.
However it is interesting to  show that this
is indeed true in a different (and quick) manner. The issue 
here is to show that the total number of 
trivial 1--inner and  0--inner contributions cannot exceed
the number of 3--inner, 2--inner contributions and external
bubbles after the overall contraction. In fact, whenever we contract a trivial 1--inner
or 0--inner self-loop, we split the one-vertex graph in $m_1 = 2$ or
$m_0= 3$ one-vertex (non discs) graphs and get either a power of $z^{-3}$
or $z^{-7}$, respectively. On each of these resulting 
graphs, we can pursue the contraction. But, at the 
end, either we are led to a connected component of the form 
of a 3--inner self-loop and we gain a power of $z^{5}$
per connected component obtained, 
or to a final vertex with only flags (see Lemma \ref{lem:fullcont}). 
The simplest non trivial vertex-graph 
with the minimal number of external bubbles is given $\mathcal{G}_1$ in Figure \ref{fig:npb} and yields $B_{{\rm ext}}(\mathcal{G}_1)=3$. 
Call $\beta_3$ the number of components yielding 
a 3--inner self-loop and $\beta_x$ the number of components
yielding an empty vertex graph. Then 
\begin{equation}
\beta_3 + \beta_x = 2n_1 + 3n_0\,,
\qquad 
\beta_3 \leq n_3\,, \qquad 3\beta_x \leq B_{{\rm ext}}(\mathcal{G}^0)\,,
\end{equation}
and hence 
\begin{eqnarray}
-3n_1 -7n_0 + 5n_3 + 2 B_{{\rm ext}}(\mathcal{G}^0)
&\geq& 
-3n_1 -7n_0 + 5\beta_3 + 2 B_{{\rm ext}}(\mathcal{G}^0) \crcr
&\geq &7n_1 +8n_0 + 2(B_{{\rm ext}}(\mathcal{G}^0)-5\beta_x/2) \geq 0\,.
\end{eqnarray}
In all situation, we can always beat the negative power introduced
by the trivial $0-$ or $1$--inner edge. 




$\bullet$ Studying the limit cases, we have the following reduced polynomials: 
for a w-colored graph $\mathfrak{G}$ and any representative $\mathcal{G}$ of $\mathfrak{G}$,  
\begin{equation}
\mathfrak{T}_{\mathcal{G}} (x,y,z=1,s=1,w=1,q=1,t) = \mathcal{T}_{\mathcal{G}}(x,y,t)\,, 
\end{equation}
where, computing $\mathcal{T}$ for $\mathcal{G}$, we consider in its simple
graph (collapsed) form.

There is a priori no direct mapping between $\mathfrak{T}$ and BR polynomials
(with and without flags) because these two polynomials have a different
``dimensionality'' or rank with respect to stranded structures. One might
think about a combinatorial manipulation by collapsing the tensor structure to a ribbon graph by removing a strand. This deserves to be fully
understood. However, in order to find
such a mapping with BR polynomials, a natural way would be to define the classes of ``rank 2'' w-colored graphs and their associated polynomials. 
These latter should coincide with 
$\mathcal{R}$ and $\mathcal{R}'$ after identifications and reduction of some variables. There will be nothing more general than $\mathcal{R}$ and $\mathcal{R}'$ in such context. The point raised in rank $D\geq 3$ is the presence of $p\geq 3$-bubbles.


\vspace{0.4cm}

Few important properties have to be addressed: 
\vspace{0.1cm}

$\bullet$ The {\bf universality} property of $\mathfrak{T}$, $\mathfrak{T}'$
or $\mathfrak{T}''$ which is the fact
that any other function satisfying \eqref{tenscondel} and \eqref{tensbri}
can be expressed in terms of one of these polynomial 
needs to be understood. This task is not performed in this work which 
has mainly focused on the definition of the relevant
graph objects for which a polynomial invariant can be identified. 
The universality will be addressed in a forthcoming work
and will require a complete understanding of the one-vertex
w-colored graphs as they appear in the formalism. 
We think that the introduction
of colors will help in reducing the type of graph structures  
that we need to classify.  
Hence, we aim at finding suitable classes 
of graphs for which one of the polynomials $\mathfrak{T}$, $\mathfrak{T}'$ 
or $\mathfrak{T}''$ will prove to be universal. 


$\bullet$ In fact, before addressing the universality issue on stranded structures, one first needs to understand to what 
extent the universality property can be recovered for 
the extension $\mathcal{R}$ of the BR polynomial 
for ribbon graphs with flags (without pinching). 
This will amount to generalize the notion of chord diagrams 
$\mathcal{D}$,
their equivalence relation under rotations about chords and finally 
their associated basic canonical diagrams $\mathcal {D}_{ijk}$ (counting 
the nullity $i$, genus $j$ of the diagram, $k$ is associated with
the orientation of the surface associated with diagram) \cite{bollo,bollo3}
to chord diagrams with flags. Such a preliminary task 
will certainly imply the existence of a new canonical diagram 
$\mathcal {D}_{ijkl}$, where $i$, $j$, $k$ keep their meaning and 
$l$ defines the number of connected component associated
with the boundary of the open ribbon graph.  


$\bullet$ There exists another formulation of the Tutte and 
BR polynomials in terms of spanning tree expansions. Such a notion 
deserves to be investigated as well in the context of w-colored
stranded graphs.  




\begin{center}
{\bf Acknowledgements}
\end{center}

{\footnotesize Discussions with Vincent Rivasseau at early stage
of this work are gratefully acknowledged. RCA thanks the Perimeter Institute for its hospitality.
Research at Perimeter Institute is supported by the Government of Canada through Industry
Canada and by the Province of Ontario through the Ministry of Research and Innovation.
This work is partially supported by the Abdus Salam International Centre for Theoretical Physics (ICTP, Trieste, Italy) through the Office of External Activities (OEA)-Prj-15. The ICMPA is also in partnership with the Daniel Iagolnitzer Foundation (DIF), France.}


