Edge coloring of small signed graphs

Abstract

In 2020, Behr introduced the problem of edge coloring of signed graphs and proved that every signed graph (G, sigma) can be colored using Delta(G) or Delta(G) + 1 colors, where Delta(G) denotes the maximum degree of G. Three years later, Janczewski et al. introduced a notion of signed class 1, such that a graph G is of signed class 1 if and only if every signed graph (G, sigma) can be colored using Delta(G) colors.

It is a well-known fact that almost all graphs are of class 1. In this paper we conjecture that the similar fact is true for signed class 1, that almost all graphs are of signed class 1. To support the hypothesis we implemented an application that colored all the signed graphs with at most 8 vertices. We describe an algorithm behind the application and discuss the results of conducted experiments.