=Paper=
{{Paper
|id=Vol-1623/paperco13
|storemode=property
|title=Pq-König Extended Forests and Cycles
|pdfUrl=https://ceur-ws.org/Vol-1623/paperco13.pdf
|volume=Vol-1623
|authors=Dmitry Mokeev
|dblpUrl=https://dblp.org/rec/conf/door/Mokeev16
}}
==Pq-König Extended Forests and Cycles==
https://ceur-ws.org/Vol-1623/paperco13.pdf
Pq -König Extended Forests and Cycles
Dmitry B. Mokeev1,2,?
1
National Research University Higher School of Economics, Laboratory of Algorithms and
Technologies for Networks Analysis, 136 Rodionova Str., Nizhny Novgorod, Russia 603093
2
National Research Lobachevsky State University of Nizhni Novgorod, 23 Gagarina Ave.,
Nizhny Novgorod, 603950, Russia
Abstract. A graph is König for a q-path if every its induced subgraph has the
following property. The maximum number of pairwise vertex-disjoint induced
paths each on q vertices is equal to the minimum number of vertices, such that
removing all the vertices produces a graph having no an induced path on q
vertices. In this paper, for every q ≥ 5, we describe all König graphs for a q-
path obtained from forests and simple sycles by replacing some vertices into
graphs not containing induced paths on q vertices.
1 Introduction
Let F be a set of graphs. A set of pairwise vertex-disjoint induced subgraphs of a
graph G each isomorphic to a graph in F is called a F-matching of G. The F-matching
problem is to find a maximum F-matching in a graph. A subset of vertices of a graph
G which covers all induced subgraphs of G each isomorphic to a graph in F is called a
vertex cover of G with respect to F or simply its F-cover. In other words, removing all
vertices of any F-cover of G produces a graph that does not contain none of the graphs
in F as an induced subgraph. The F-cover problem is to find a minimum F-cover in
a graph. A König graph for F is a graph in which every induced subgraph has the
property that the maximum cardinality of its F-matching is equal to the maximum
cardinality of its F-cover [1]. The class of all König graphs for a set F is denoted as
K(F). If F consists of a single graph H, then we will talk about H-matchings, H-covers,
and König graphs for H, respectively.
One can find some similar terms in the literature: ”König-Egervary graph” [2], ”a
graph with the König property” [3], ”König graph” [4] . They all mean a graph in which
the cardinalities of a maximum matching and a minimum vertex cover are equal. The
known König Theorem claims that the class of bipartite graphs is exactly the class of
all graphs whose cardinalities of a maximum matching and a minimum vertex cover
are equal not only for a graph but also for all its induced subgraphs. Note that our
definition of a König graph is not a generalization of the notion in [2,3,4], because we
?
This article is partially supported by Russian Foundation for Basic Research (grants 16-31-
00109-mol-a, 16-01-00599-a), by RF President grant MK-4819.2016.1, by LATNA labora-
tory, National Research University Higher School of Economics.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
Pq -König Extended Forests and Cycles 87
require the equality of the parameters in all induced subgraphs of a graph. Thus, the
class of bipartite graphs coincides with the class of all König graphs for P2 in this sense.
A lot of papers on the F-matching problem are devoted to algorithmic aspects (see
[5,6,7,8]). It is known that the Matching problem (i.e., P2 -matching problem) can be
solved in polynomial time [9], but the H-matching problem is NP-complete for any
graph H having a connected component with three or more vertices.
It seems perspective to find new polynomially solvable cases for the F-matching
and F-cover problems in the context of the method of critical graph classes developed
in the papers of V. E. Alekseev and D. S. Malyshev [10]–[18].
Being formulated as the integer linear programming problems, the F-matching and
F-cover problems form a pair of dual problems. So, König graphs are graphs, such that
for any their induced subgraph there is no a duality gap for the problems above. In
this regard, König graphs are similar to perfect graphs having the same property with
respect to another pair of dual problems (vertex coloring and maximum clique) [19],
which helps to solve efficiently these problems on perfect graphs [20].
Every hereditary class X can be described by a set of its minimal forbidden induced
subgraphs, i.e. minimal by the relation “to be an induced subgraph” graphs not be-
longing to X . A class K(F) is hereditary for any F and therefore it can be described
by a set of forbidden induced subgraphs. Such a characterization for K (P2 ) is given
by the König theorem. In addition to this classical theorem, the following results are
known. All minimal forbidden induced subgraphs for the class K(C) are described in
[21], where C is the set of all simple cycles. All minimal forbidden induced subgraphs
for the class K(P3 ) are described, and full structural description of this class is given
in [1,22]. Several families of forbidden induced subgraphs for K(P4 ) are found, and it
was conjectured that these families form a complete set of minimal forbidden induced
graphs for this class in [23]. A structural description for one of the subclasses of K(P4 )
is given in [24]. Graphs of this subclass can be obtained from graphs of a special type by
replacing vertices with cographs, i.e., graphs not containing induced paths on 4 vertices.
The aim of this paper is to extend the structural description in [1,22,24] to some
simple subclasses of K(Pq ) for any q ≥ 5. In section 2, we define the procedure of
a R-Fq -extention of graphs. In section 3, we show how to obtain König graphs for
Pq applying this procedure to forests. Moreover, in section 4, we find some forbidden
induced subgraphs and show what graphs obtained from simple cycles by the R-Fq -
extention are König for Pq .
In what follows we consider induced Pq with q ≥ 5. The maximum number of
subgraphs in Pq -matchings of G is denoted as µPq (G), and the minimum number of
vertices in its Pq -covers as βPq (G).
A q-path is an induced subgraph isomorphic to Pq . We denote by (v1 , v2 , . . . , vq ) a
q-path that consists of vertices v1 , v2 , . . . , vq . We denote by Fq the class of graphs not
containing q-paths.
We denote by |G| the number of vertices in G. We denote by N (x) the neighbour-
hood of a vertex x in a graph.
We denote by G ∪ H the graph obtained from graphs G and H with non-intersected
sets of vertices by their union. We denote by G − v the graph obtained from G by
deleting a vertex v with all incident edges.
88 D.B. Mokeev
Considering a cycle Cn , we assume that its vertices are clockwisely numbered as
0, 1, ..., n − 1. The arithmetic operations with the vertex numbers are performed
modulo n. Every residue class of vertex numbers for modulo q is called a q-class.
2 R-Fq -extention of graphs
In this section, we define the R-Fq -extention of graphs and describe the basic properties
of graphs obtained by this procedure.
Definition 1. The operation of replacement of a vertex x in a graph G with a graph
H, where V (G) ∩ V (H) = ∅, consists of the following. We take a graph (G − x) ∪ H
and add all edges connecting V (H) with N (x).
A homogeneous set in a graph G is a set A ⊆ V (G), such that every vertex of
V (G)\A is either adjacent to all vertices of A or to none of them. A homogeneous set
is trivial if it is equal to V (G) or consists of one vertex and non-trivial, otherwise.
Definition 2. Let X be a class of graphs. The operation of a R-X -extention of G
consists of the following. Every vertex of degree 1 or 2 is replaced with an arbitrary
graph of X .
Definition 3. A section with a base x denoted by S(x) is the set of vertices of the
graph by which we replaced x. Every vertex not replaced with any graph is considered
as a separate section.
Obviously, any section is a homogeneous set. A section is trivial if it consists of one
vertex and non-trivial, otherwise.
We say that two sections S(x) and S(y) are adjacent in a R-Fq -extention of a graph
G if x and y are adjacent in G. Obviously, if S(x) and S(y) are adjacent, then each
vertex of S(x) is adjacent to each vertex of S(y).
Lemma 1. If a set of vertices A induce Pq in a R-Fq -extention of a graph G, then
|A ∩ S(x)| = 1 for all x ∈ V (G).
Proof. Every section induces a subgraph from Fq . Then the set A can not be entirely
contained in any section. Since any section is a homogeneous set, if a section S(x)
contains two or more vertices of A, then the set A∩S(x) is a non-trivial homogeneous set
in the subgraph induced by A. But a q-path does not contain a non-trivial homogeneous
set for any q > 3.
Lemma 2. Every minimum Pq -cover of any R-Fq -extention of any graph consists of
whole sections.
Proof. Let C be a minimum Pq -cover of an R-Fq -extention of some graph G. Suppose
that there exists a section which contains vertices x ∈ C and y 6∈ C. Since C is a
minimum Pq -cover, there exists a set A ⊆ V (G) inducing Pq , such that A ∩ C =
{x}. Otherwise, the vertex x can be deleted from C. By Lemma 1, y 6∈ A. But then
A\{x} ∪ {y} induce Pq , but it does not contain vertices of C.
Pq -König Extended Forests and Cycles 89
3 R-Fq -extended forests
In this section, we consider graphs obtained by a R-Fq -extention of forests. We will
prove that all such graphs are König for Pq .
Theorem 1. For any q, every R-Fq -extention F̃ of a forest F is a König graph for
Pq .
Proof. The proof is by induction on the number of q-paths in F̃ . If there is no a q-path,
then µPq (F̃ ) = βPq (F̃ ) = 0. Now consider F̃ which contains at least one q-path. By
Lemma 1, all vertices of this q-path are contained in different sections. Obviously, they
induce Pq in F .
Let T be a connected component of F containing a q-path. Let us select an arbitrary
root r of T having degree three or more, if one exists. If T is a simple path, then r is
one of its leaves.
Speaking about trees, we consider that they are drawn in a bottom-up manner from
roots to leaves. For every q-path in T , a bottom vertex is the closest to r vertex of this
q-path. Let a be the farther from r bottom vertex for all q-paths. There exists a q-path
0
X which consists of a and descendants of a. Let T be a subtree of T with the root a.
0
Then in T every q-path contains the vertex a.
Let X = {x1 , . . . , xk } be a set of vertices inducing Pq in T with the bottom vertex
a. Obviously, a is a member of this set. Let us select an arbitrary vertex yi in every
section S(xi ). It is easy to see that Y = {y1 , . . . , yk } induce Pq in F̃ . Delete all vertices
0
of Y from F̃ . Denote obtained graph as F̃ . It contains less q-paths than F̃ . By the
0
induction hypothesis, there exists a Pq -matching M of F̃ and its Pq -cover C, such that
|P | = |C|. Then M ∪ {Y } is the Pq -matching of F̃ of the cardinality |M | + 1.
For a Pq -cover of F̃ , we have two cases:
0 0 0
1. C contains at least one of the sections S (x1 ), . . . , S (xk ), where S (xi ) =
0 0
S(xi )\{yi }. Suppose that C contains sections S (xi ) and S (xj ), where i 6= j.
If the vertex xi is an ancestor of xj in the tree T , then every q-path, intersected
0 0 0
with S (xj ) intersects S (xi ) as well. Therefore, C\S (xj ) is a Pq -cover of F̃ 0 .
Now suppose that xi , xj are not ancestors of each other. Then they have a common
ancestor xl in T . Obviously, xl is a descendant of a or equals to a. Since degree of
0
xl is three or more, |S (xl ) | = 1. In this
case, every q-path
intersected with S (xi )
0 0 0
or S (xj ) contains xl . Therefore, C\ S (xi ) ∪ S (xj ) ∪ {xl } is a Pq -cover of the
0
graph F̃ . 0
Thus, if C is a minimum Pq -cover of the graph F̃ , then C contain exactly one of
0 0 0
the sections S (x1 ), . . . , S (xk ). Let S (xi ) be a such section. Then C ∪ {yi } is a
Pq -cover of F̃ .
0 0
2. None of the sections S (x1 ), . . . , S (xk ) is a subset of C. Then at least one of
0 0
S (x1 ), . . . , S (xk ) is empty. Let b denote the highest common ancestor of xi with
0
S (xi ) = ∅. Then either b = a or b is a descendant of a and every section between
a and b consists of more than one vertex. In the both cases, every q-path of F̃ with
bottom vertex in S(a) contains the vertex b and other q-paths are covered by the
set C. Thus, C ∪ {b} is a Pq -cover of F̃ .
90 D.B. Mokeev
So, for the both cases, there exists a Pq -cover of the graph F̃ of the cardinality |M |+
1. But, every induced subgraph of F̃ is an R-Fq -extention of some forest. Therefore, F̃
is a König graph for Pq .
4 R-Fq -extended cycles
4.1 Common cases for forbidden induced graphs
Now we consider the graphs obtained by applying a R-Fq -extention to simple cycles.
We call them R-Fq -extended cycles.
Considering a R-Fq -extention of a cycle Cn , we assume that the sections are clock-
wisely numbered as 0, 1, ..., n − 1. Every residue class of sections numbers for modulo
q is called a q-class.
At first, we define several infinite families of forbidden induced subgraphs for K(Pq )
for every q ≥ 5.
Obviously, for any k > 1
pack (Cqk ) = µPq (Cqk+1 ) = · · · = µPq (Cqk+q−1 ) = k;
cover (Cqk ) = βPq (Cqk−1 ) = · · · = βPq (Cqk−q+1 ) = k.
Note that every proper induced subgraph of a simple cycle is a forest. By Theorem 1,
it is a König graph for Pq . Hence, the following lemma is valid.
Lemma 3. A cycle Cn belongs to K(Pq ) if n is divisible by q, and Cn is a minimal
forbidden induced subgraph for K(Pq ) if n is not divisible by q.
Thus, a R-Fq -extention of a simple cycle can be a König graph for Pq only if the
basic cycle has a number of vertices divisible by q.
Let k1 , k2 , . . . , kq be arbitrary naturals, such that k1 + k2 + · · · + kq = qn. Let
us chose q vertices in a cycle Cqn in such a way that its paths containing no the
chosen vertices except their endpoints have lengths k1 , k2 , . . . , kq . We replace any
chosen vertex into an arbitrary two-vertex graph. The set of all resultant graphs
is denoted by D̃q (k1 , k2 , . . . , kq ). Let Dq (k1 , k2 , . . . , kq ) denote any graph of the set
D̃q (k1 , k2 , . . . , kq ).
Pi
Let denote ri = j=1 kj . Obviously, one can enumerate vertices along the cycle in
such a way that the replaced vertices have numbers 0, r1 , . . . rq−1 .
Definition 4. A graph D(k1 , k2 , . . . , kq ) is crowded if ∀i, j : ri 6≡ rj (mod q). It means
that exactly one vertex is replaced with a two-vertex graph in every q-class of the basic
cycle.
Definition 5. A T-array in a R-Fq -extended cycle is a maximal collection of sequen-
tially adjacent trivial sections. Similarly, a N-array in a R-Fq -extended cycle is a max-
imal collection of sequentially adjacent non-trivial sections. A size of a T-array or a
N-array is a number of sections in it.
Pq -König Extended Forests and Cycles 91
Definition 6. A vector of array sequence (AS-vector for short) of a graph
Dq (k1 , k2 , . . . , kq ) is a sequenced collection of numbers (u1 , t1 , u2 , t2 , . . . , um , tm ), where
for all i ∈ {1, . . . , m} ti is lenght of T-array and ui is lenght of N-array.
For example, the AS-vector for the graph D9 (1, 3, 1, 16, 10, 7, 15, 19, 1) is
(3, 2, 2, 15, 1, 9, 1, 6, 1, 14, 1, 18).
Note that AS-vector of every graph Dq (k1 , k2 , . . . , kq ) has the properties:
m
X m
X
ui = q, ti = q(n − 1).
i=1 i=1
The arithmetic operations with the indexes in an AS-vector are performed modulo
m.
Theorem 2. A crowded graph Dq (k1 , k2 , . . . , kq ) is a minimal forbidden induced sub-
graph for K(Pq ) if and only if for its AS-vector (u1 , t1 , u2 , t2 , . . . , um , tm ) there exists
a number i, such that ui + ti + ui+1 6≡ 0 (mod q).
Proof. For every crowded graph D, βPq (D) = n + 1, where qn is length of the basic
cycle. We show that for every crowded graph D µPq (D) = n + 1 if and only it in its
AS-vector for every i ui + ti + ui+1 is divisible by q and µPq (D) = n, otherwise.
Let Dq (k1 , k2 , . . . , kq ), where k1 + k2 + · · · + kq = qn, be a crowded graph. Its
number of vertices equals to qn + q. It means that a Pq -matching of the cardinality
n + 1 must include all vertices of the graph. It is easy to see that every N-array have
to begin one of q-paths and end one of q-path of such Pq -matching. In other words, it
can not lie in the middle of any q-path of the Pq -matching. Moreover, if the end of a
q-path of the Pq -matching belongs to a trivial section, then the beginning of the next
q-path belongs strictly to the next section. It is possible only if the number of sections
between the beginning of a N-array and the end of the next one is divisible by q, i.e.
∀i ui + ti + ui+1 = q. Otherwise, no one Pq -matching includes all vertices of the graph
and the maximum cardinality of Pq -matchings is equal to n.
Every induced subgraph of a crowded graph is a R-Fq -extended forest or a R-Fq -
extended cycle, such that one of its q-classes consists of trivial sections only. In the
both cases, the graph is König for Pq . So, every crowded graph D with µPq (D) = n is
a minimal forbidden induced subgraph for K(Pq ).
Notice that for every q ≥ 3 the minimum number of sections in crowded graphs
is equal to 2q. For example, for any odd q a graph Dq (2, 2, . . . , 2) (Fig. 1) has
the minimum possible number of sections. Similarly, for every even q, a graph
Dq (2, 2, . . . , 2, 1, 2, 2, . . . , 2, 3) is also extremal. By Theorem 2, for any q ≥ 5, this
| {z } | {z }
q q
2 −1 2 −1
graphs are minimal forbidden induced subgraphs for K(Pq ).
92 D.B. Mokeev
Figure 1. One of the graphs D5 (2, 2, 2, 2, 2)
4.2 Main theorem about R-Fq -extended cycles
For every Pq , let Dq denote the set of the crowded graphs that are minimal forbidden
induced subgraphs for K(Pq ).
Now we prove that Dq is a complete set of forbidden induced subgraphs for R-Fq -
extended cycles, which are König graphs for Pq .
Theorem 3. A R-Fq -extended cycle is a König graph for Pq if and only if it does not
include induced subgraphs belonging to the set Dq .
Proof. Let G be obtained from a simple cycle Cqn by replacing its vertices with Fq -
graphs, and any its induced subgraph does not belong to the set Dq . By Theorem 1, any
R-Fq -extended tree it is König for P4 . Every induced subgraph of G is a R-Fq -extended
cycle with the same property or an R-Fq -extended tree. Thus, it is enough to prove
that there exist a Pq -matching and a Pq -cover of equal cardinalities in G.
The proof is by induction on the number of q-paths in the graph. Let every q-path
in G intersect at least one trivial section. It means that deleting a q-path always induce
a R-Fq -extended forest. The following cases are possible.
1. G does not contain induced crowded graphs. Then there is at least one q-class
consisting of only trivial sections. Obviously, this q-class gives a Pq -cover of G of
the cardinality q. A Pq -matching of the same cardinality coincides with one of the
maximum Pq -matchings of the basic cycle.
2. G contains N-array of lenght q − 1. Let it consist of the sections S1 , S2 , . . . , Sq−1 .
0
Then we consider a graph G obtained from G by deletion of sections S0 , S1 , . . . , Sq .
0
The graph G is a R-Fq -extended tree. Therefore, by Theorem 1, there exist a Pq -
0 0 0
matching M and a Pq -cover C of G of equal cardinalities.
Pq -König Extended Forests and Cycles 93
In what follows, for each i ∈ {0, nq − 1}, let ui denote an arbitary vertiex of a
section Si , and vi denote an another vertex of the same section, if one exists.
0
It is easy to see that M = M ∪ {(u0 , u1 , . . . uq−1 ) , (v1 , v2 , . . . vq−1 , uq )} is the Pq -
0 0
matching of graph G, and C = C ∪S0 ∪Sq is its Pq -cover and |M | = |C| = M +2
3. G contains a crowded induced subgraph and the maximum size l of N-arrays is
more than 2 and no more than q − 2. Suppose that a N-array of the maximum size
consists of sections S1 , S2 , . . . , Sl . Assume that a section Sqi+2 is non-trivial for
some i ≥ 1. Then G contains a crowded induced subgraph, such that its AS-vector
contains a sequence uj , tj , uj+1 , where uj = 1, tj = 1, uj+1 = l − 2. The sum of
this parameters is l. By Theorem 2, such graph must be forbidden. Thus, sections
Sq+2 , S2q+2 , . . . S(n−1)q+2 are trivial. Note that sections S0 and Sl+1 are trivial as
well. Let us consider a set
n−1
[
C= Sqi+2 ∪ S0 ∪ Sl+1 .
i=1
It is easy to see that C is a Pq -cover of G and |C| = n + 1. But none crowded
induced subgraph of G is forbidden. Therefore, by proof of Theorem 2, it contains
a Pq -matching M of the cardinality n + 1. Obviously, M is a Pq -matching of graph
G.
4. G contains a crowded induced subgraph and every N-array of G consists of no more
than 2 sections. Consider two neighbour N-arrays of some crowded subgraph D of
G. Let the first of them begin from S1 . It means that the section S1 of the graph
G is non-trivial. By Theorem 2, the next N-array ends in section, which number is
divisible by q. In other words, for G there exists l, such that Sql is non-trivial.
0
Let l > 1. Consider a graph D obtained from D by adding a vertex into the section
Sq+3 and deleting one vertex from the non-trivial section of the same q-class. The
0
AS-vector of the graph D contains a sequence ui , ti , ui+1 , such that their sum is
0
equal to q + 3. By Theorem 2, D must be forbidden. Thus, the section Sq+3 is
trivial in G. Similarly, all sections S2q+3 , S3q+3 , . . . S(l−1)q+3 are trivial in G. Since
every N-array consists of no more than 2 sections, the section S3 is trivial as well.
Similarly, if Sr is the begin section of some N-array of a crowded induced subgraph
of G and Sr+x is the begin section of its next N-array, then for 0 < x − hq − 2 < q,
all sections Sr+2 , Sr+q+2 , . . . Sr+hq+2 of the graph G are trivial. By Theorem 2,
x ≡ q − 1(mod q) if the N-array consists of one section or x ≡ q − 2(mod q) if it
consists of two sections.
Consider an AS-vector (u1 , t1 , u2 , . . . , um , tm ) of the graph D. Let u1 correspond
to the N-array, which begins from the section S1 . Denote r0 = 1, ri = ri−1 + ui + ti
for all i ∈ {1, . . . , m − 1}, hi is the number, such that 0 < ri+1 − ri − hi q − 2 < q.
It is easy to see that
m [
[ hi
C= Sri +jq+2
i=0 j=0
is a P −q-cover of the graph G and |C| = n+1. But none crowded induced subgraph
of G is forbidden. Therefore, by proof of Theorem 2, it contains a Pq -matching M
of the cardinality n + 1. Obviously, M is a Pq -matching of the graph G.
94 D.B. Mokeev
Thus, if every q-path of the graph G intersects at least one trivial section, then G
is a König graph for Pq .
Now let some q-path of the graph G intersect only non-trivial sections. Since for
q ≥ 5, there exists a crowded forbidden graph having 2q sections, every R-Fq -extended
cycle, which consists of only non-trivial sections, contains a crowded forbidden induced
subgraph. Thus, G contains at least one trivial section. Suppose that S0 is a trivial
section and S1 , S2 , . . . , Sq are non-trivial sections in G.
0
Let us select one vertex vi from each section Si , i ∈ {1, . . . , q}. Let G denote a
graph obtained from G by deleting vertices v1 , v2 , . . . , vq . By the induction hypothesis,
0 0 0 0
G contains a Pq -matching M and a Pq -cover C of equal cardinalities. Note that C
contains at least one section among Si \ {vi } , i ∈ {1, . . . , q}, but no more than 2. If there
0 0
are two such sections, then S0 is not a subset of C . Otherwise C is not minimum. Then
0
we change section with the minimum number into S0 in C . The obtained Pq -cover is a
minimum Pq -cover, which contains exactly one section among Si \ {vi } , i ∈ {1, . . . , q}.
0 0
We add to C the deleted vertex of the corresponding section. We add to M the q-
path (v1 , v2 , . . . , vq ). The obtained sets are some Pq -cover and some Pq -matching of the
graph G of equal cardinalities.
References
1. Alekseev V. E., Mokeev D. B.: König graphs with respect to 3-paths. Diskretnyi Analiz i
Issledovanie Operatsii. 19.4, 3–14 (2012)
2. Deming R. W.: Independence numbers of graphs – an extension of the König-Egervary
theorem. Discrete Math. 27, 23–33 (1979)
3. Lovasz L., Plummer M. D.: Matching Theory. Akadémiai Kiadó, Budapest (1986)
4. Mishra S., Raman V., Saurabh S., Sikdar S., Subramanian C. R.: The Complexity of König
Subgraph Problems and Above-Guarantee Vertex Cover. Algorithmica. 61, 857–881 (2011)
5. Hell P.: Graph packing. Electron. Notes Discrete Math. 5, 170–173 (2000)
6. Yuster R.: Combinatorial and computational aspects of graph packing and graph decom-
position. Comput. Sci. Rev. 1, 12–26 (2007)
7. Malyshev D. S.: The impact of the growth rate of the packing number of graphs on the
computational complexity of the independent set problem. Discrete Mathematics and Ap-
plications. 23.3–4, 245–249 (2013)
8. Malyshev D. S.: Boundary classes of graphs for some problems of recognition. Diskretnyi
Analiz i Issledovanie Operatsii. 16(2), 85–94 (2009)
9. Edmonds J.: Paths, trees, and flowers. Canadian Journal of mathematics. 17.3–4, 449–467
(1965)
10. V. E. Alekseev: On easy and hard hereditary classes of graphs with respect to the inde-
pendent set problem. Discrete Applied Mathematics 132 (2004) 17–26.
11. Malyshev D. S.: Continued sets of boundary classes of graphs for colorability problems.
Diskretnyi Analiz i Issledovanie Operatsii 16.5 4151 (2009)
12. Malyshev D.: Classes of graphs critical for the edge list-ranking problem. Journal of Ap-
plied and Industrial Mathematics. 8.2, 245–255 (2014)
13. Malyshev D.: On the number of boundary classes in the 3-colouring problem. Discrete
Mathematics and Applications. 19.6, 625–630 (2010)
14. Malyshev D.: A Study of the Boundary Graph Classes for Colorability Problems. Journal
of Applied and Industrial Mathematics. 7.2, 221–228 (2013)
Pq -König Extended Forests and Cycles 95
15. Malyshev D.: Boundary graph classes for some maximum induced subgraph problems.
Journal of Combinatorial Optimization. 27.2, 345–354 (2014)
16. Malyshev D., Pardalos P. M.: Critical hereditary graph classes: a survey. Optimization
Letters. 10.1007/s11590-015- 0985-1 (2016)
17. N. Korpelainen, V. V. Lozin, D. S. Malyshev, A. Tiskin: Boundary properties of graphs
for algorithmic graph problems. Theoretical Computer Science. 412.29, 3545-3554 (2011)
18. D. S. Malyshev: On minimal hard classes of graphs. Diskretnyi Analiz i Issledovanie Op-
eratsii. 16.6, 43–51 (2009)
19. Berge C.: Graphs and hypergraphs. Vol. 7. Amsterdam: North-Holland publishing com-
pany. (1973)
20. Grötschel M., Lovasz L., Schrijver A.: Geometric algorithms and combinatorial optimiza-
tion. Springer-Verlag, Heidelberg (1993)
21. Ding G., Xu Z., Zang W.: Packing cycles in graphs II. J. Comb. Theory. Ser. B. 87,
244–253 (2003)
22. Alekseev V. E., Mokeev D. B.: König graphs for 3-paths and 3-cycles. Discrete Applied
Mathematics. 204, 1–5 (2016)
23. Mokeev D.: König Graphs for 4-Paths. Models, Algorithms and Technologies for Network
Analysis, Springer, 93–103 (2014)
24. Mokeev D.: König Graphs for 4-Paths II. Models, Algorithms and Technologies for Net-
work Analysis, Springer, in press (2016)
25. Chvatal V.: A semi-strong perfect graph conjecture. Annals of Discrete Mathematics. 21,
279–280 (1984)