Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs (Q2093879)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs |
scientific article |
Statements
Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs (English)
0 references
27 October 2022
0 references
This paper investigates the structure of \(P_6\)-free chordal bipartite graphs and gives a polynomial-time algorithm for finding a Hamiltonian cycle. This problem is known to be NP-hard for general chordal bipartite graphs. The paper even gives polynomial-time algorithms for the Hamiltonian path, longest path, and longest cycle in this graph subclass. The authors also extend known results for the \(P_5\)-free chordal bipartite graphs by showing that the feedback vertex set, vertex cover, and clique cover are polynomial for \(P_5\)-free chordal bipartite graphs.
0 references
\(P_6\)-free chordal bipartite graphs
0 references
Hamiltonian cycle (path)
0 references
longest cycle (path)
0 references
\(P_5\)-free chordal bipartite
0 references
feedback vertex set
0 references
vertex cover
0 references
clique cover
0 references