Edge coloring of small signed graphs

• Autorzy: Janczewski Robert , Turowski Krzysztof , Wróblewski Bartłomiej

Identyfikatory

DOI

10.34808/tsdg-z467

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph; graph edge; graph coloring

PL

graf; krawędź grafu; kolorowanie grafów

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2023
• Tom: Vol. 27, No 2
• Strony: 1--9
• Opis fizyczny: Bibliogr. 9 poz., tab., rys.

Twórcy

autor

Janczewski Robert

• Department of Algorithms and System Modeling, Faculty of ElectronicsTelecommunication and Informatics, Gdańsk University of Technology, ul. Narutowicza 11/12, Gdańsk, Poland

autor

Turowski Krzysztof

• Theoretical Computer Science Department, Jagiellonian University, Kraków, 30–348, Poland

autor

Wróblewski Bartłomiej

• Gdańsk University of Technology, ul. Narutowicza 11/12, Gdańsk, Poland

Bibliografia

• [1] R. Behr, “Edge coloring signed graphs”, Discrete Mathematics, vol. 343, no. 2, p. 111654, 2020.
• [2] R. Janczewski, K. Turowski, and B. Wróblewski, “Edge coloringof graphs of signed class 1 and 2”, Discrete Applied Mathematics, vol. 338, pp. 311–319, 2023.
• [3] P. Erdős and R. Wilson, “On the chromatic index of almost allgraphs”, Journal of Combinatorial Theory, Series B, vol. 23, pp. 255–257, 1977.
• [4] R. Diestel, Graph Theory. Springer-Verlag Berlin Heidelberg, 2017.
• [5] F. Harary, “On the notion of balance of a signed graph”, Michigan Mathematical Journal, vol. 2, pp. 143–146, 1953.
• [6] R. Naserasr, E. Sopena, and T. Zaslavsky, “Homomorphisms of signed graphs: An update”, European Journal of Combinatorics, vol. 91, p. 103222, 2021.
• [7] R. Behr, “Edge coloring signed graphs,” 2018.
• [8] B. McKay and A. Piperno, “Practical graph isomorphism, ii”, Journal of Symbolic Computation, vol. 60, pp. 94–112, 2014.
• [9] V. Vizing, “Critical graphs with a given chromatic class”, Diskret. Analiz, vol. 5, pp. 9–17, 1965.