Strong pseudo transitivity and intersection graphs

MaRDI QIDQ5224759zbMATH OpenFDO

Authors Farhad Shahrokhi

Publication date 24 July 2019

Full work available at URL https://arxiv.org/abs/1806.01378

zbMATH Keywords

maximum independent set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A directed graph $G=(V,E)$ is {it strongly pseudo transitive} if there is a partition $A,E-A$ of $E$ so that graphs $G_1=(V,A)$ and $G_2=(V,E-A)$ are transitive, and additionally, if $abinA$ and $bcinE$ implies that $acinE$. A strongly pseudo transitive graph $G=(V,E)$ is strongly pseudo transitive of the first type, if $abinA$ and $bcinE$ implies $acinA$. An undirected graph is co-strongly pseudo transitive (co-strongly pseudo transitive of the first type) if its complement has an orientation which is strongly pseudo transitive (co-strongly pseudo transitive of the first type). Our purpose is show that the results in computational geometry cite{CFP, Lu} and intersection graph theory cite{Ga2, ES} can be unified and extended, using the notion of strong pseudo transitivity. As a consequence the general algorithmic framework in cite{Sh} is applicable to solve the maximum independent set in $O(n^3)$ time in a variety of problems, thereby, avoiding case by case lengthily arguments for each problem. We show that the intersection graphs of axis parallel rectangles intersecting a diagonal line from bottom, and half segments are co-strongly pseudo transitive. In addition, we show that the class of the interval filament graphs is co-strongly transitive of the first type, and hence the class of polygon circle graphs which is contained in the class of interval filament graphs (but contains the classes of chordal graphs, circular arc, circle, and outer planar graphs), and the class of incomparability graphs are strongly transitive of the first type. For class of chordal graphs we give two different proofs, using two different characterizations, verifying that they are co-strongly transitive of the first type. We present some containment results.

Recommendations

• scientific article; zbMATH DE number 4200260
• Algorithms for longest chains in pseudo-transitive graphs
• scientific article; zbMATH DE number 867674
• The edge intersection graphs of paths in a tree
• scientific article; zbMATH DE number 3912430

This page was built for publication: Strong pseudo transitivity and intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224759)