Enumerative aspects of certain subclasses of perfect graphs
type: Item
instance of: scholarly article
title: Enumerative aspects of certain subclasses of perfect graphs
zbMATH Open document ID: 0936.05058
DOI: 10.1016/S0012-365X(99)00022-9
author: Venkatesan Guruswami
published in: Discrete Mathematics
publication date: 2000-04-26T00:00:00Z
review text: The author considers the enumerative aspects of various graph classes such as \(P_4\)-free graphs, \((C_4, 2K_2, C_5)\)-free graphs, \((P_4, C_4)\)-free graphs, and \((P_4,C_4,2K_2)\)-free graphs. In particular, he determines the number of permutations \(\pi\) of \(1,2, \ldots, n\) such that the permutation graph defined by \(\pi\) is a \(P_4\)-free graph, respectively, a \((P_4,C_4,2K_2)\)-free graph. The author also considers the class of \((C_4,2K_2)\)-free graphs and gives a charaterization of these graphs (Theorem 4.1) which is already known in the literature; see, for example, \textit{Z. Blázsik} et al. [Graphs with no induced \(C_4\) and \(2K_2\), Discrete Math. 115, No.~1-3, 51-55 (1993; Zbl 0772.05082)] and \textit{F. Maffray} and \textit{M. Preissmann} [Linear recognition of pseudo-split graphs, Discrete Appl. Math. 52, No.~3, 307-312 (1994; Zbl 0805.05069)].
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05E10
Mathematics Subject Classification ID: 05C17
zbMATH DE Number: 1334681
zbMATH Keywords: generating functions
zbMATH Keywords: isomorphism
zbMATH Keywords: perfect graph
zbMATH Keywords: output-restricted deque
zbMATH Keywords: permutation graph
zbMATH Keywords: cograph
zbMATH Keywords: Young tableaux
zbMATH Keywords: Polya's enumeration theory
MaRDI profile type: Publication
cites work: Enumeration of labelled threshold graphs and a theorem of Frobenius involving Eulerian polynomials
cites work: A Linear Recognition Algorithm for Cographs
cites work: Q4193514
cites work: Trivially perfect graphs
cites work: Q3328583
cites work: Q5682013
cites work: Q3862379
cites work: Permutations, matrices, and generalized Young tableaux
cites work: Q4057549
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: Threshold graphs and related topics
cites work: Enumeration of difference graphs
cites work: Q3922688
cites work: Longest Increasing and Decreasing Subsequences
cites work: Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
cites work: A Note on "The Comparability Graph of a Tree"
Wikidata QID: Q128011541
description: scientific article; zbMATH DE number 1334681