A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs (Q2168862)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs |
scientific article |
Statements
A note on shortest sign-circuit cover of signed 3-edge-colorable cubic graphs (English)
0 references
26 August 2022
0 references
A sign-circuit cover \(F\) of a signed graph (G; \(\sigma\)) is a family of sign-circuits which covers all edges of (G; \(\sigma\)). The shortest sign-circuit cover problem was initiated by \textit{E. Máčajová} et al. [J. Graph Theory 81, No. 2, 120--133 (2016; Zbl 1332.05066)] and received much attention in recent years. A well-known conjecture, the shortest cycle cover conjecture, was proposed by \textit{N. Alon} and \textit{M. Tarsi} [SIAM J. Algebraic Discrete Methods 6, 345--350 (1985; Zbl 0581.05046)]. Here, the authors show that every flow-admissible signed 3-edgecolorable cubic graph (G; \(\sigma\)) has a sign-circuit cover with length at most \(\frac{20}{9}|E(G)|\). The authors pose the problem to determine the optimal upper bound for the shortest sign-circuit cover of a signed 3-edge-colorable cubic graph that remains open. This paper has many interesting results and many future problems are posed. This will help many young researchers working in the area of signed graphs. I have advised younger researchers to read this paper.
0 references
signed graph
0 references
sign-circuit cover
0 references
cubic graph
0 references
colorable graph
0 references
upper bound
0 references