Logo image
Back
On the P3-convexity of some classes of graphs with few P4S and permutation graphs
Conference paper

On the P3-convexity of some classes of graphs with few P4S and permutation graphs

Wing-Kai Hon, Ton Kloks and Hsiang-Hsuan Liu
ACM International Conference Proceeding Series, Vol.01-05-February-2016, a24
01/02/2016
DOI: https://doi.org/10.1145/2843043.2843055

Abstract

Carathéodory number Graphs and convexities P3-convexity Permutation graphs
We analyze the P 3 -geodetic number, the P 3 -hull number and the P 3 -Carathéodory number for tree-cographs, and these parameters for P 4 -reducible graphs. We also show that the P 3 hull number is polynomial for permutation graphs. Moreover, we give monadic second-order formulas for the P 3 -hull and P 3 -Carathéodory numbers in general, thus showing that these parameters are polynomial for graphs of bounded rankwidth or treewidth.

Metrics

1 Record Views

Details

Logo image