Abstract
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.
Similar content being viewed by others
References
V. E. Alekseev and D. B. Mokeev, “König Graphs with Respect to 3-Paths,” Diskretn. Anal. Issled. Oper. 19 (4), 3–14 (2012).
D. S. Malyshev, “The Impact of the Growth Rate of the Packing Number of Graphs on the Computational Complexity of the Independent Set Problem,” Diskretn. Mat. 25 (2), 63–67 (2013) [Discrete Math. Appl. 23 (3–4), 245–249 (2013)].
D. S. Malyshev, “Classes of Graphs Critical for the Edge List-Ranking Problem,” Diskretn. Anal. Issled. Oper. 20 (6), 59–76 (2013) [J. Appl. Indust. Math. 8 (2), 245–255 (2014)].
V. E. Alekseev, “On Easy and Hard Hereditary Classes of Graphs with Respect to the Independent Set Problem,” Discrete Appl. Math. 132 (1–3), 17–26 (2004).
V. E. Alekseev and D. B. Mokeev, “König Graphs for 3-Paths and 3-Cycles,” Discrete Appl. Math. 204, 1–5 (2016).
D. G. Corneil, H. Lerchs, and L. Stewart Burlingham, “Complement Reducible Graphs,” Discrete Appl. Math. 3 (3), 163–174 (1981).
G. Ding, Z. Xu, and W. Zang, “Packing Cycles in Graphs, II,” J. Combin. Theory, Ser. B 87 (2), 244–253 (2003).
J. Edmonds, “Paths, Trees, and Flowers,” Can. J. Math. 17 (3–4), 449–467 (1965).
P. Hell, “Graph Packings,” Electron. Notes Discrete Math. 5, 170–173 (2000).
D. G. Kirkpatrick and P. Hell, “On the Completeness of a Generalized Matching Problem,” in Proceedings of X Annual ACM Symposium on Theory of Computing, San Diego, USA, May 1–3, 1978 (ACM, New York, 1978), pp. 240–245.
N. V. R. Mahadev and U. N. Peled, Threshold Graphs and Related Topics (North Holland, Amsterdam, 1995).
D. B. Mokeev, “König Graphs for 4-Paths,” in Models, Algorithms and Technologies for Network Analysis: Proceedings of 3th International Conference on Network Analysis, Nizhny Novgorod, Russia, May 20–22, 2013 (Springer, Cham, 2014), pp. 93–103.
R. Yuster, “Combinatorial and Computational Aspects of Graph Packing and Graph Decomposition,” Comput. Sci. Rev. 1 (1), 12–26 (2007).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © D.B. Mokeev, 2017, published in Diskretnyi Analiz i Issledovanie Operatsii, 2017, Vol. 24, No. 3, pp. 61–79.
Rights and permissions
About this article
Cite this article
Mokeev, D.B. On König graphs with respect to P4 . J. Appl. Ind. Math. 11, 421–430 (2017). https://doi.org/10.1134/S1990478917030139
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1990478917030139