Signed Colorings

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:

(1)
\begin{align} \chi(G)\equiv\sum_{\kappa}\mathrm{sgn}(\kappa). \end{align}

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

(2)
\begin{align} \chi(G)=\sum_{\sigma\in S_n}\mathrm{sgn}(\sigma)=0, \end{align}

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$:

(3)
\begin{align} \chi_{\kappa_E}(G)=\sum_{\kappa\succ\kappa_E} sgn_\kappa(G). \end{align}

Example.

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

Exercises

Exercise. exercise

Exercise. exercise

page revision: 5, last edited: 28 Aug 2008 01:00