Finding a path with two labels forbidden in group-labeled graphs

DOI10.1016/j.jctb.2019.12.001zbMath1437.05208arXiv1807.00109OpenAlexW2995652579MaRDI QIDQ2173429

Yutaro Yamaguchi, Yusuke Kobayashi, Yasushi Kawase

Publication date: 22 April 2020

Published in: Journal of Combinatorial Theory. Series B, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.00109

zbMATH Keywords

group-labeled graph\(s-t\) path2-disjoint pathsnon-zero path

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (3)

Finding a path with two labels forbidden in group-labeled graphs ⋮ Space Complexity of Reachability Testing in Labelled Graphs ⋮ Space complexity of reachability testing in labelled graphs

Cites Work

• Unnamed Item
• Packing non-zero \(A\)-paths via matroid matching
• Packing cycles with modularity constraints
• Packing non-zero \(A\)-paths in group-labelled graphs
• An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• 2-linked graphs
• Pólya's permanent problem
• Graph minors. XIII: The disjoint paths problem
• Permanents, Pfaffian orientations, and even directed circuits
• Finding a path with two labels forbidden in group-labeled graphs
• A unified Erdős-Pósa theorem for constrained cycles
• Non-zero disjoint cycles in highly connected group labelled graphs
• Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity
• Graph Theory
• The even-path problem for graphs and digraphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Efficient Planarity Testing
• Modularity of cycles and paths in graphs
• Packing A-paths in Group-Labelled Graphs via Linear Matroid Parity

This page was built for publication: Finding a path with two labels forbidden in group-labeled graphs