.

Browsing SoAS - Scholarly Publications by Author "Feghali, Carl"

LAUR Repository

Browsing SoAS - Scholarly Publications by Author "Feghali, Carl"

Sort by: Order: Results:

  • Forbidden subgraph characterization of (P3-free, K3-free)-colourable cographs 
    Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko (2018-04-26)
    A (P3-free, K3-free)-colouring of a graph G = (V, E) is a partition of V = A ∪ B such that G[A] is P3-free and G[B] is K3-free. This problem is known to be NP-complete even when restricted to planar graphs and perfect ...
  • NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph 
    Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko (2018-04-26)
    This paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. This problem is known to be NP-complete on ...
  • Partitioning a graph into degenerate subgraphs 
    Abu-Khzam, Faisal N.; Feghali, Carl; Heggernes, Pinar (2018-04-26)
    Let G = (V, E) be a connected graph with maximum degree k ≥ 3 distinct from Kk+1. Given integers s ≥ 2 and p1, . . . , ps ≥ 0, G is said to be (p1, . . . , ps)-partitionable if there exists a partition of V into sets V1, ...
  • Partitioning a graph into disjoint cliques and a triangle-free graph 
    Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko (2015-12-07)
    A graph G=(V,E) is partitionable if there exists a partition {A,B} of V such that A induces a disjoint union of cliques (i.e. , G[A] is P3-free) and B induces a triangle-free graph (i.e. , G[B] is K3-free). In this ...

Search LAUR


Advanced Search

Browse

My Account