, Theorem 5.2 It is N P-complete to decide whether an undirected graph G = (V, E) has a vertex partition
,
, ? Add new vertices ? 1
, ? Add new vertices ? 1
, Note that, by construction, for every good partition every vertex of G which is not in R must belong to V 2 . In particular if a path P i,j contains a vertex of V 2 then all the vertices of P i,j are in V 2 . Since we want G[V 2 ] to be connected, the edges between ? i , ? i , i ? [n] and R imply that for every i ? [n] at most one of the vertices a i,1 , a i,2 and a most one of the vertices b i,1 , b i,2 can belong to V 1 . This implies that exactly one of a i,1 , a i,2 and exactly one of the vertices b i,1 , b i,2 belong to V 1 as otherwise V 1 would be empty. Now it is easy to check that the desired partition exists if and only if R contains a cycle C which uses precisely one of the paths P i,1 , P i,2 for i ? [n] and avoids at least one literal vertex for every clause of F. Thus, by Theorem 2.2, F is satisfiable if and only if G has a good partition, We claim that the resulting graph G has a vertex partition
, ) such that G[V i ] is connected and has a cycle for i = 1, 2 if and only if G has a pair of disjoint cycles and either G is connected or it has exactly two connected components
, Theorem 5.4 It is N P-complete to decide whether a graph G = (V, E) has a vertex partition
, G(F) be the graph we constructed in the proof above. Let G 1 be the graph obtained by adding the following vertices and edges to G: ? add new vertices c j , j ? [m], q j , j ? {0}
, c m q m ? complete this path into a cycle W by adding the edges ?q 0 , ?q m ? add an edge from ? to all vertices in {? 1
, Splitting digraphs, Combin. Prob. Comput, vol.15, pp.933-937, 2006.
, Finding good 2-partitions of digraphs II. Enumerable properties, Theor. Comput. Sci, vol.640, pp.1-19, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01346079
, Digraphs: Theory, Algorithms and Applications, 2009.
, Finding good 2-partitions of digraphs I. Hereditary properties, Theor. Comput. Sci, vol.636, pp.85-94, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01327015
, The satisfactory partition problem, Discrete Appl. Math, vol.154, issue.8, pp.1236-1245, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00004258
, Degree-constrained decompositions of graphs: Bounded treewidth and planarity, Theor. Comput. Sci, vol.355, issue.3, pp.389-395, 2006.
, Efficient algorithms for decomposing graphs under degree constraints, Discrete Applied Mathematics, vol.155, issue.8, pp.979-988, 2007.
, On the complexity of partitioning a graph into a few connected subgraphs, J. Combin. Optim, vol.30, pp.174-187, 2015.
URL : https://hal.archives-ouvertes.fr/hal-00762612
, Extremal Graph Theory, 1978.
, Recognizing graphs close to bipartite graphs, 42nd International Symposium on Mathematical Foundations of Computer Science, vol.70, 2017.
, Independent feedback vertex sets for graphs of bounded diameter, Information Proc. Letters, vol.131, pp.26-32, 2018.
, Graph Theory, vol.244, 2008.
, Recognizing decomposable graphs, J. Graph Theory, vol.8, issue.1, pp.51-53, 1984.
, On the complexity of partitioning graphs into connected subgraphs, Discrete. Appl. Math, vol.10, pp.139-153, 1985.
, Split graphs, Congress. Numer, vol.19, pp.311-315, 1977.
, Algorithmic approach to the satisfactory graph partitioning problem, European J. of Operation Research, vol.125, pp.283-291, 2000.
, Classes of graphs that can be partitioned to satisfy all their vertices, Australasian J. of Combin, vol.29, pp.201-214, 2004.
, Connected feedback vertex set in planar graphs, WG 2009: Graph Theoretical concepts in Computer Science, vol.5911, pp.143-153, 2009.
, Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, vol.3, pp.95-99, 1983.
, On decomposition of triangle-free graphs under degree constraints, J. Graph Theory, vol.27, issue.1, pp.7-9, 1998.
, Partitions of graphs with high minimum degree or connectivity, J. Combin. Theory Ser. B, vol.88, pp.29-43, 2003.
, Splitting a graph into disjoint induced paths or cycles, Discrete. Appl. Math, vol.131, pp.199-212, 2003.
, On partitions of graphs under degree constraints, Disc. Appl. Math, vol.226, pp.87-93, 2017.
, Bipartition of graph under degree constraints, Science China Mathematics, vol.58, pp.869-874, 2015.
, On graphs not containing independent circuits, MatLapok, vol.16, p.289299, 1965.
, Decomposing C 4 -free graphs under degree constraints, 2017.
, FPT algorithms for connected feedback vertex set, J. Combin. Optim, vol.24, pp.131-146, 2012.
, Decomposition of graphs and digraphs, KAM Series in Discrete Mathematics-Combinatorics-Operations Research-Optimization 95-309, 1995.
, Decomposing graphs under degree constraints, J. Graph Theory, vol.23, pp.321-324, 1996.
, A linear algorithm for bipartion of biconnected graphs, Inform. Process. Lett, vol.33, pp.227-231, 1990.
, Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, vol.7, pp.165-167, 1983.
, Paths, circuits and subdivisions, Selected topics in graph theory, vol.3, pp.97-131, 1988.
, Partitioning graphs into connected parts, Theor. Comput. Sci, vol.410, pp.4834-4843, 2009.
, Complexity and kernels for bipartition into degree-bounded induced graphs, Theor. Comput. Sci, vol.659, pp.72-82, 2017.