ISGCI project home  All classes  Smallgraphs

Graphclass: P4-indifference

Definition:
A graph is P4-indifference if it admits an acyclic orientation in which each induced P4 is of the type: o->o->o->o

References: [571]
Equivalent classes:  (A,E,S3,X1,domino,hole,house,net,rising sun)-free 
Complement classes:  (P5,S3,co-(A),co-(E),co-(X1),anti-hole,co-domino,co-rising sun,net)-free 
Related classes:  P4-comparability   P4-simplicial   bipolarizable   indifference 

Inclusions

Minimal superclasses:  AT-free   (C6,C8,T2,X3,co-(BW3),co-(W5),co-(W7),co-(X103),co-(X105),co-(X106),co-(X107),co-(X108),co-(X109),co-(X110),co-(X111),co-(X112),co-(X113),co-(X114),co-(X115),co-(X116),co-(X117),co-(X118),co-(X119),co-(X120),co-(X121),co-(X122),co-(X123),co-(X124),co-(X125),co-(X126),co-(X53),co-(X88),co-X104)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,X37,X38,X39,X40,X41,XF2n+1,XF3n,XF4n)-free   (Cn+6,T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,co-XF12n+3,co-XF52n+3,co-XF62n+2,odd anti-hole)-free   E-free   HHDA-free   HHDS-free   P4-simplicial   (S3,S4,net)-free   (S3,net)-free   (S3,net)-free cap sun-free   (T2,X2,X3,X30,X31,X32,X33,X34,X35,X36,XF2n+1,XF3n,XF4n,anti-hole,co-XF12n+3,co-XF52n+3,co-XF62n+2,hole)-free   (anti-hole,co-sun,hole)-free   co-comparability   hereditary homogeneously orderable   (house,hole,domino,sun)-free   weak bipolarizable 
Maximal subclasses:  (2,0)-colorable cap chordal   (2K2,C4,C5,S3,co-rising sun,net,rising sun)-free   (2K2,C4,C5,S3,net,rising sun)-free   (2P3,3K2,C4,C5,H,P2 cup P4,P5,S3,X1,X160,co-(X159),co-(X161),co-(X162),co-(X46),co-(X70),net,rising sun)-free   (3K1,C4,C5)-free   (C4,odd anti-cycle)-free   (C5,P,P5,S3,co-(P),co-fork,fork,house,net)-free   (Cn+4,P5,bull)-free   (Cn+4,S3,claw,net)-free   (Cn+4,XF2n+1,XF3n,claw)-free   P4-extendible cap P4-sparse   P4-reducible   (P5,bull)-free cap interval   (S3,claw,net)-free cap chordal   astral triple-free   chordal cap co-chordal cap co-comparability cap comparability   chordal cap unit circular arc   claw-free cap interval   co-interval cap interval   co-probe threshold   homogeneously representable   indifference   permutation cap split   proper interval   split cap threshold signed   unit interval 

Problems summary

Recognition:Lineardetails
Cliquewidth expression: Unbounded or NP-complete details
Cliquewidth:Unboundeddetails
Weighted independent set:Polynomialdetails
Independent set:Lineardetails
Domination:Polynomialdetails

Algorithms for Recognition

Linear [1224] [1225]

Algorithms for Cliquewidth expression

See also : Cliquewidth : Weighted independent set : Domination

Algorithms for Cliquewidth

Unbounded from unit interval  [1177]
See also : Cliquewidth expression

Algorithms for Weighted independent set

Polynomial [O(n^4)] from AT-free  [160]
Polynomial from interval filament  [1159]
Polynomial from perfect  [476]
Polynomial [O(V^4)] from weakly chordal  [997]
Polynomial from subtree overlap  [1123]
See also : Cliquewidth expression : Independent set

Algorithms for Independent set

Linear from co-comparability  [1100]
Polynomial [O(VE)] from weakly chordal  [530] [1119]
Polynomial from Meyniel  [169]
See also : Weighted independent set

Algorithms for Domination

Polynomial from co-comparability  [1150] [1151]
Polynomial from AT-free  [1152]
See also : Cliquewidth expression