HOSIGRA

Frustration Index

A state of a signed graph is to assign + or - to its vertices (think of - vertices as those on which a switching will be applied). Given a signed graph together with an state an edge is said to be satisfied if the product of its signed with the sign of two ends is +. An edge that is not satisfied is called frustrated. The smallest number of frustrated edges over all states is called the frustration index. It is equivalently the minimum number of negative edges among all equivalent signatures and also minimum number of edges to cover all negative cycles.

A signed graph is critically k-frustrated if its frustration index is k and every proper subgraph has smaller frustration index.

Examples for frustration critical signed graphs are anti-balanced odd wheels.

What can be said about planar critical graphs or classes defined by forbidden minors? For planar graphs, the dual problem is a minimum T-join problem.

Question (Chiara, Eckhard): Is it true that, up to some basic operations (subdivisions), there are only finitely many critically $k$-frustrated graphs?

Student in charge of the project: Chiara.

Signature packing number

This time given a signed graph we want the max number of equivalent signatures no pair of which have a common negative edge.

To see the importance of the subject consider the following which is (nontrivially) a restatement of the four-color theorem.

For every simple planar graph the associated signed graph where all edges are negative has signature packing number at least 3.

That this is equivalent to the 4CT is a good homework.

Counterexamples to Macajova-Raspaud-Skoveira conjecture, first of which was built by of Kardos-Narboni, leads to examples of planar signed simple graphs whose packing number is 1.

Student in charge of the project: Weiqiang

Problems we may look at:

1. Lower and upper bounds based on structural information.

2. Study of the corresponding and related polytopes.

Circular coloring and circular flow

Circular r-coloring of a signed graph is to assign open intervals of length 1 from a circle C of circumference r to the vertices of the signed graph such that for each pair of vertices connected by a negative edge the corresponding intervals do not share any point and if they are adjacent with a positive edge, then antipodal interval of one does not intersect the interval of the other.

Taking the dual notion on planar graphs we have the natural circular-flow notion.

Remark. In this notion of flow, each edge is directed in one direction. The difference with circular flow on graphs is having two different types of forbidden values.

Student lead of the project: Zhouningxin

Problems we may look at:

Many directions to follow from here. A particular one of interest:

Given the Kneser graph K(p,q) what is the largest possible circular chromatic number among all signatures? For K(5,2), the Petersen graph, this is 10/3, that is slightly bigger than the chromatic number which is 3.

Color critical signed (simple) graphs

A signed graph is said to be p/q-critical if it does not admit a circular p/q-coloring, but any proper subgraph of it does. This extends the notion of k-critical graphs; recall that traditionally a k-critical graph is a graph of chromatic number k whose all proper subgraphs are (k-1)-colorable. Using the notion on signed graphs G is k-critical if the signed graph (G, +) is (k-1)-critical.

A general question then is to study the structural properties of p/q-critical signed graphs. For example what are the minimum and maximum numbers of edges in a p/q-critical signed graph on n vertices? How does the answer change with a given girth condition?

It follows from Theorem 6 of "The chromatic number of signed graph, by E. Macajova, A. Raspaud, M. Skoveira" that for even values of Δ the only Δ-critical signed graphs are complete balanced graphs, positive odd cycles and negative even cycles. We expect that a similar proof works for odd values of Δ.

The question that remains is for which values of Δ and ε there exist (Δ-ε)-critical signed graphs. Perhaps for Δ large enough and ε small enough there are no such signed graphs. That would be an extension of Borodin-Kostochka conjecture.

Nowhere-zero flow on Dowling Matroids

A Dowling Matroid is a Matroid M that is representable over a field F by a n x E(M) matrix A so that no column has more than two non-zero entries. This representation A is a Dowling representation. It can be thought of as the incidence matrix of a graph* G in the regular way, but so that each half-edge comes with an associated value given by the matrix. G is then a generalization of a signed graph. Ie: when F is the field of order two, G is a signed graph. For the below question, say a flow in G is, as usual, a vector in the null space of A, and let the flow take values in the multiplicative group of F.

Question (DeVos): Does every co-loop free Dowling representation over the field of order 7 have a nowhere-zero flow?

Perhaps other signed graph problems can be asked in terms of Dowling representations? Ex: Circular colourings.

Student in charge of the project: Kathryn