Duchet-type theorems for powers of HHD-free graphs
type: Item
instance of: scholarly article
title: Duchet-type theorems for powers of HHD-free graphs
zbMATH Open document ID: 0887.05050
DOI: 10.1016/S0012-365X(96)00370-6
author: Andreas Brandstädt
author: Van Bang Le
author: Thomas Szymczak
published in: Discrete Mathematics
publication date: 1998-04-28T00:00:00Z
review text: The \(k\)th power of a graph \(G\), denoted \(G^k\), is the graph with the vertex set \(V(G)\) in which two vertices are adjacent if their distance in \(G\) is at most \(k\). The authors prove three results of ``Duchet-type''; that is, results which read: ``If \(G^k\) contains no induced subgraph of a certain type (say, long cycles), then so does \(G^{k+2}\).'' They do so by employing an idea of Duchet: One can define a new graph \((G^k)(X)\), with vertices certain subsets of \(V(G)\), that is isomorphic to \(G^{k+2}\), and work out the results in \((G^k)(X)\).
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1110104
zbMATH Keywords: powers of graphs
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Distances in cocomparability graphs and their powers
cites work: \(r\)-dominating cliques in graphs with hypertree structure
cites work: Convexity and HHD-Free Graphs
cites work: Powers of hhd-free graphs∗
cites work: Q3222876
cites work: Q4323316
cites work: On powers of \(m\)-trapezoid graphs
cites work: On sources in comparability graphs, with applications
cites work: Weak bipolarizable graphs
cites work: An nc algorithm to recognize hhd-free graphs
cites work: Q3783331
cites work: Q4032992
full work available at URL: s0012-365x(96)00370-6
OpenAlex ID: W2117307792
Recommended article: Powers of hhd-free graphs∗
Recommended article: A proof of Hougardy's conjecture for diamond-free graphs
Recommended article: A new characterization of HH-free graphs
Recommended article: Erdős-Hajnal-type theorems in hypergraphs
Recommended article: Brooks' theorem on powers of graphs
Recommended article: Powers of connected graphs and hamiltonicity
Recommended article: The \(H\)-spectra of a class of generalized power hypergraphs
Recommended article: Graph Powers, Delsarte, Hoffman, Ramsey, and Shannon
Recommended article: Hajós' conjecture and cycle power graphs
Recommended article: Convexity and HHD-Free Graphs
description: scientific article; zbMATH DE number 1110104