Edge coloring of small signed graphs
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Gdańsk University of Technology
2025-01-01
|
| Series: | TASK Quarterly |
| Subjects: | |
| Online Access: | https://journal.mostwiedzy.pl/TASKQuarterly/article/view/3071 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841553399810621440 |
|---|---|
| author | Robert Janczewski Krzysztof Turowski Bartłomiej Wróblewski |
| author_facet | Robert Janczewski Krzysztof Turowski Bartłomiej Wróblewski |
| author_sort | Robert Janczewski |
| collection | DOAJ |
| description |
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.
|
| format | Article |
| id | doaj-art-a1d5af0067564455871c1dcd3659a96f |
| institution | Kabale University |
| issn | 1428-6394 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Gdańsk University of Technology |
| record_format | Article |
| series | TASK Quarterly |
| spelling | doaj-art-a1d5af0067564455871c1dcd3659a96f2025-01-09T10:23:55ZengGdańsk University of TechnologyTASK Quarterly1428-63942025-01-01272Edge coloring of small signed graphsRobert Janczewski0Krzysztof Turowski1Bartłomiej Wróblewski2Gdańsk University of Technology, ul. Narutowicza 11/12, Gdańsk, PolandTheoretical Computer Science Department, Jagiellonian University, Kraków, 30–348, PolandGdańsk University of Technology, ul. Narutowicza 11/12, Gdańsk, Poland 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. https://journal.mostwiedzy.pl/TASKQuarterly/article/view/3071signed graphedge coloring of signed graph |
| spellingShingle | Robert Janczewski Krzysztof Turowski Bartłomiej Wróblewski Edge coloring of small signed graphs TASK Quarterly signed graph edge coloring of signed graph |
| title | Edge coloring of small signed graphs |
| title_full | Edge coloring of small signed graphs |
| title_fullStr | Edge coloring of small signed graphs |
| title_full_unstemmed | Edge coloring of small signed graphs |
| title_short | Edge coloring of small signed graphs |
| title_sort | edge coloring of small signed graphs |
| topic | signed graph edge coloring of signed graph |
| url | https://journal.mostwiedzy.pl/TASKQuarterly/article/view/3071 |
| work_keys_str_mv | AT robertjanczewski edgecoloringofsmallsignedgraphs AT krzysztofturowski edgecoloringofsmallsignedgraphs AT bartłomiejwroblewski edgecoloringofsmallsignedgraphs |