Compatible spanning circuits and forbidden induced subgraphs

DOI10.1007/s00373-023-02735-8OpenAlexW4391033100MaRDI QIDQ6184989

Maximilian Geißer, Christoph Brause, Ingo Schiermeyer, Zhi-Wei Guo

Publication date: 29 January 2024

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-023-02735-8

zbMATH Keywords

Hamiltonian graphedge-colored graphsupereulerian graphforbidden subgraphcompatible spanning circuit

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Eulerian and Hamiltonian graphs (05C45) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hamilton cycles in 5-connected line graphs
• Forbidden pairs for spanning (closed) trails
• Some algorithmic results for finding compatible spanning circuits in edge-colored graphs
• The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index
• On a closure concept in claw-free graphs
• Forbidden triples for Hamiltonicity
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Compatible Eulerian circuits in Eulerian (di)graphs with generalized transition systems
• Hamiltonicity and minimum degree in 3-connected claw-free graphs
• Compatible spanning circuits in edge-colored graphs
• Almost Eulerian compatible spanning circuits in edge-colored graphs
• Forbidden set of induced subgraphs for 2-connected supereulerian graphs
• Hamiltonicity of digraphs for universal cycles of permutations
• A note on Hamiltonian circuits
• A note on graphs spanned by Eulerian graphs
• Hamiltonian results inK1,3-free graphs
• Hamilton cycles in claw-free graphs
• A reduction method to find spanning Eulerian subgraphs
• Supereulerian graphs: A survey
• A Note on Sub-Eulerian Graphs
• Sufficient Conditions for a Digraph to be Supereulerian
• The Orderly Colored Longest Path Problem – a survey of applications and new algorithms
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results