This page introduces the idea of a signed coloring of a graph, which applies to only very special kinds of graphs.

## Fat Graphs

**Definition.** For positive integers $n$, an *$n$-fat graph* is a graph $G$ whose vertices have degree either $1$ or $n$. In addition, at every vertex with degree $n$ the edges are ordered. We refer to the degree-$1$ vertices as *leaves* and the degree-$n$ vertices as *$n$-vertices*.

When these graphs are drawn on a sheet of paper (or in the plane), the ordering at a vertex may be uniquely specified by drawing a small dot between two edges at the vertex. The edges are then enumerated by proceeding in a counter-clockwise fashion. This marking is sometimes called a *ciliation*, and so fat graphs are sometimes also called *ciliated graphs*.

In the following fat graph, the edges at the lower vertex have ordering $(a\:b:\:e\:d)$ and at the upper vertex have ordering $(d\:e\:c\:f)$:

## Fat Graph Colorings and Pre-Colorings

**Definition.** An *admissible coloring* of an $n$-fat graph is a labeling of its edges by $n$ different "colors" in such a way that at each $n$-vertex all colors are different.

An admissible coloring induces a permutation of $\{1,2,\ldots,n\}$ at each vertex of a fat graph, obtained by reading off the $n$ colors in the order of edges at the vertex. In the example above…

**Definition.** The *signature* $\mathrm{sgn}(\kappa)$ of an admissible coloring $\kappa$ of an $n$-fat graph is the product of signatures of the permutations at the vertices induced by the coloring. If the graph has no $n$-vertices, the signature of every coloring is defined to be 1.

**Example.** `example of signature for one possible coloring`

In what follows, we will want to restrict our attention to colorings where the colors along a certain set of edges is fixed. Alternately, we will have a set of edges that are colored, and will want to find colorings of the entire fat graph that extend this coloring.

**Definition.** A *pre-coloring* $\kappa_E$ of an $n$-fat graph $G$ is an assignment of colors to a subset of edges $E$ of $G$ such that no two colored edges adjacent to the same vertex have the same color. Given an admissible coloring $\kappa$, if each edge in $E$ has the same label in $\kappa_E$ as in $\kappa$, we say that $\kappa$ *extends* $\kappa_E$ and write $\kappa\succ\kappa_E$.

**Example.**

## The Signed Chromatic Index

In traditional graph theory, coloring questions are often related to the number of ways a certain graph can be colored with $n$ different colors. For fat graphs, the corresponding question takes into account the signature of each coloring.

**Definition.** The *signed chromatic index* $\chi(G)$ of an $n$-fat graph $G$ is the sum of signatures of the graph over all possible colorings:

**Example.** If a graph consists of a single edge, there are $n$ possible colorings of the graph. Since there are no vertices, the signature is $+1$, so the signed chromatic index is $+n$.

**Example.** If a graph consists of a single $n$-vertex (and no edges loop back to the vertex), then there are $n!$ possible colorings, and the signed chromatic index is

since for $n\ge2$ the number of even permutations on $n$ elements is equal to the number of odd permutations.

**Definition.** Given a pre-coloring $\kappa_E$ of $G$, the *pre-chromatic index* $\chi_{\kappa_E}(G)$ is the sum of signatures over all colorings that extend $\kappa_E$:

**Example.**

Actually, this notion is not very useful since it nearly always works out to be 0.

## Exercises

**Exercise.** `exercise`

**Exercise.** `exercise`