Cycles through two edges in signed graphs

EUROCOMB’23

Abstract
We give a characterization of when a signed graph $G$ with a pair of distinguished edges $e_1, e_2 \in E(G)$ has the property that all cycles containing both $e_1$ and $e_2$ have the same sign. This answers a question of Zaslavsky.

Pages:
349–354
References

A. Bouchet. Nowhere-zero integral flows on a bidirected graph. J. Combin. Theory Ser. B, 34(3):279-292, 1983.
https://doi.org/10.1016/0095-8956(83)90041-2

Guantao Chen, Ronald J. Gould, and XingXing Yu. Graph connectivity after path removal. Combinatorica (Budapest. 1981), 23(2):185-203, 2003.
https://doi.org/10.1007/s003-0018-z

Roland Häggkvist and Carsten Thomassen. Circuits through specified edges. Discrete mathematics, 41(1):29-34, 1982.
https://doi.org/10.1016/0012-365X(82)90078-4

Kenichi Kawarabayashi. One or two disjoint circuits cover independent edges: Lovász-woodall conjecture. Journal of combinatorial theory. Series B, 84(1):1-44, 2002.
https://doi.org/10.1006/jctb.2001.2059

Kenichi Kawarabayashi, Orlando Lee, Bruce Reed, and Paul Wollan. A weaker version of lovász' path removal conjecture. Journal of combinatorial theory. Series B, 98(5):972-979, 2008.
https://doi.org/10.1016/j.jctb.2007.11.003

Matthias Kriesell. Induced paths in 5-connected graphs. Journal of graph theory, 36(1):52-58, 2001.
https://doi.org/10.1002/1097-0118(200101)36:1<52::AID-JGT5>3.0.CO;2-N

László Lovász. Problem 5. Period. Math. Hungar, 4:82, 1974.
https://doi.org/10.1007/BF02020548

László Lovász. Combinatorial problems and exercises. North-Holland, 2nd ed. edition, 1993.
https://doi.org/10.1016/B978-0-444-81504-0.50006-0

P.D. Seymour. Nowhere-zero 6-flows. Journal of combinatorial theory. Series B, 30(2):130-135, 1981.
https://doi.org/10.1016/0095-8956(81)90058-7

W.T. Tutte. How to draw a graph. Proceedings of the London Mathematical Society, s3-13(1):743-767, 1963.
https://doi.org/10.1112/plms/s3-13.1.743

M.E. Watkins and D.M. Mesner. Cycles and connectivity in graphs. Canadian Journal of Mathematics, 19:1319-1328, 1967.
https://doi.org/10.4153/CJM-1967-121-2

D.R. Woodall. Circuits containing specified edges. Journal of combinatorial theory. Series B, 22(3):274-278, 1977.
https://doi.org/10.1016/0095-8956(77)90072-7

Thomas Zaslavsky. Negative circles in signed graphs: A problem collection. Electronic notes in discrete mathematics, 63:41-47, 2017.
https://doi.org/10.1016/j.endm.2017.10.060

Metrics

0

Views

0

PDF views