Open Access Open Access  Restricted Access Subscription Access

Characterizing the Existence of P4

Pinaki Mitra


In a graph G = (V, E) P4 denotes a path of length 4 vertices <v1, v2, v3, v4> such that there is no edge between either <v1, v3> or <v2, v4>. This exists either in graph G = (V, E) or its complement or both for which both G and the complement Gc are connected. In this article we give a proof for this property.


P4, Complement graph, star Sub-graph, induction

Full Text:



Corneil D.G., Lerchs H., Burlingham L.

Stewart. Complement reducible graphs,

Discrete Applied Mathematics 1981;


Corneil D. G., Perl Y., Stewart L. K., A

linear recognition algorithm for cographs,

SIAM Journal on Computing 1985; 14(4):

(1985) 926–934.

Jamison B., Olariu S., P4-reducible graphs,

a class of uniquely tree representable

graphs. Studies in Applied Mathematics

; 81: 79–87p.

Jamison B., Olariu S., A tree

representation for P4-sparse graphs.

Discrete Applied Mathematics 1992;

(2): 115–129p.

Jamison B., Olariu S., Recognizing P4-sparse graphs in linear time, SIAM Journal on Computing 1992; 21(2):381–406p.

Jamison B., Olariu S., Linear time optimization algorithms for P4-sparse graphs Discrete Applied Mathematics 1995; 61(2): 155–175p.


  • There are currently no refbacks.