Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

1 2023

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Edge coloring of small signed graphs

Janczewski Robert, Turowski Krzysztof, Wróblewski Bartłomiej

TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk

2023

Vol. 27, No 2

1--9

In 2020, Behr [1] introduced the problem of edge coloring of signed graphs and proved that every signed graph (G, σ) can be colored using ∆(G) or ∆(G) +1colors, where ∆(G) denotes the maximum degree of G. Three years later, Janczewski et al. [2] introduced a notion of signed class 1, such that a graph G is of signed class 1 if and only if everysigned graph (G, σ) can be colored using ∆(G) colors. It is a well-known fact [3] that almost all graphs are of class 1. In this paper, we conjecture that a 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.