Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs
type: Item
instance of: scholarly article
title: Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs
author: R. Mahendra Kumar
author: N. Sadagopan
published in: The Journal of Analysis
publication date: 2022-10-27T00:00:00Z
review text: 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.
reviewed by: A. Shakiba
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7608560
zbMATH Keywords: \(P_6\)-free chordal bipartite graphs
zbMATH Keywords: Hamiltonian cycle (path)
zbMATH Keywords: longest cycle (path)
zbMATH Keywords: \(P_5\)-free chordal bipartite
zbMATH Keywords: feedback vertex set
zbMATH Keywords: vertex cover
zbMATH Keywords: clique cover
MaRDI profile type: Publication
full work available at URL: s41478-022-00424-y
OpenAlex ID: W4225144610
cites work: HAMILTONian circuits in chordal bipartite graphs
cites work: Hamiltonicity in Split Graphs - A Dichotomy
cites work: Q3651735
cites work: Q3888545
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Hamilton Paths in Grid Graphs
cites work: The clique-partitioning problem
DOI: 10.1007/S41478-022-00424-Y
description: scientific article; zbMATH DE number 7608560