Geodesic
On K\"onig graphs with respect to~$P_4$
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 61-79.

Voir la notice de l'article provenant de la source Math-Net.Ru

We describe the class of graphs whose every induced subgraph has the property: The maximum number of disjoint induced $4$-paths is equal to the minimum size of the set of the vertices such that each $4$-path contains at least one of them. The description is based on the operation of replacing vertices by cographs which is to the vertices of the graphs obtained from bipartite graphs by subdividing their cycle edges. Bibliogr. 13.
Keywords: packing of subgraphs, vertex covering of subgraphs, $4$-path, König graph. 
@article{DA_2017_24_3_a3,
     author = {D. B. Mokeev},
     title = {On {K\"onig} graphs with respect to~$P_4$},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {61--79},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_3_a3/}
}
TY  - JOUR
AU  - D. B. Mokeev
TI  - On K\"onig graphs with respect to~$P_4$
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 61
EP  - 79
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_3_a3/
LA  - ru
ID  - DA_2017_24_3_a3
ER  - 
%0 Journal Article
%A D. B. Mokeev
%T On K\"onig graphs with respect to~$P_4$
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 61-79
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_3_a3/
%G ru
%F DA_2017_24_3_a3
D. B. Mokeev. On K\"onig graphs with respect to~$P_4$. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 3, pp. 61-79. http://geodesic.mathdoc.fr/item/DA_2017_24_3_a3/

[1] V. E. Alekseev, D. B. Mokeev, König graphs with respect to 3-paths, 19:4 (2012), 3–14

[2] D. S. Malyshev, “The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem”, Discrete Math. Appl., 23:3–4 (2013), 245–249 | DOI | MR | Zbl

[3] D. S. Malyshev, “Classes of graphs critical for the edge list-ranking problem”, J. Appl. Ind. Math., 8:2 (2014), 245–255 | DOI | MR | Zbl

[4] Alekseev V. E., “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discrete Appl. Math., 132:1–3 (2004), 17–26 | DOI | MR

[5] Alekseev V. E., Mokeev D. B., “König graphs for 3-paths and 3-cycles”, Discrete Appl. Math., 204 (2016), 1–5 | DOI | MR | Zbl

[6] Corneil D. G., Lerchs H., Stewart Burlingham L., “Complement reducible graphs”, Discrete Appl. Math., 3:3 (1981), 163–174 | DOI | MR | Zbl

[7] Ding G., Xu Z., Zang W., “Packing cycles in graphs, II”, J. Comb. Theory, Ser. B, 87:2 (2003), 244–253 | DOI | MR | Zbl

[8] Edmonds J., “Paths, trees, and flowers”, Can. J. Math., 17:3–4 (1965), 449–467 | DOI | MR | Zbl

[9] Hell P., “Graph packings”, Electron. Notes Discrete Math. 2000, 5, 170–173 | DOI | MR

[10] Kirkpatrick D. G., Hell P., “On the completeness of a generalized matching problem”, Proc. 10th Annu. ACM Symp. Theory Comput. (San Diego, CA, May 1–3, 1978), ACM, New York, 1978, 240–245 | MR | Zbl

[11] Mahadev N. V. R., Peled U. N., Threshold graphs and related topics, Ann. Discrete Math., 56, North-Holland, Amsterdam, 1995, 543 pp. | MR

[12] Mokeev D. B., “König graphs for 4-paths”, Models, Algorithms and Technologies for Network Analysis, Proc. 3rd Int. Conf. Network Analysis (Nizhny Novgorod, Russia, May 20–22, 2013), Springer Proc. Math. Stat., 104, Springer, Cham, 2014, 93–103 | DOI | Zbl

[13] Yuster R., “Combinatorial and computational aspects of graph packing and graph decomposition”, Comput. Sci. Rev., 1:1 (2007), 12–26 | DOI | Zbl