On König graphs with respect to P₄

1. V. E. Alekseev and D. B. Mokeev, “König Graphs with Respect to 3-Paths,” Diskretn. Anal. Issled. Oper. 19 (4), 3–14 (2012).

   MathSciNet  MATH  Google Scholar 

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,” Diskretn. Mat. 25 (2), 63–67 (2013) [Discrete Math. Appl. 23 (3–4), 245–249 (2013)].

   Article  Google Scholar 

3. 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)].

   MATH  Google Scholar 

4. 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).

   Article  MathSciNet  MATH  Google Scholar 

5. V. E. Alekseev and D. B. Mokeev, “König Graphs for 3-Paths and 3-Cycles,” Discrete Appl. Math. 204, 1–5 (2016).

   Article  MathSciNet  MATH  Google Scholar 

6. D. G. Corneil, H. Lerchs, and L. Stewart Burlingham, “Complement Reducible Graphs,” Discrete Appl. Math. 3 (3), 163–174 (1981).

   Article  MathSciNet  MATH  Google Scholar 

7. G. Ding, Z. Xu, and W. Zang, “Packing Cycles in Graphs, II,” J. Combin. Theory, Ser. B 87 (2), 244–253 (2003).

   Article  MathSciNet  MATH  Google Scholar 

8. J. Edmonds, “Paths, Trees, and Flowers,” Can. J. Math. 17 (3–4), 449–467 (1965).

   Article  MathSciNet  MATH  Google Scholar 

9. P. Hell, “Graph Packings,” Electron. Notes Discrete Math. 5, 170–173 (2000).

   Article  MathSciNet  MATH  Google Scholar 

10. 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.

    Google Scholar 

11. N. V. R. Mahadev and U. N. Peled, Threshold Graphs and Related Topics (North Holland, Amsterdam, 1995).

    MATH  Google Scholar 

12. 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.

    Google Scholar 

13. R. Yuster, “Combinatorial and Computational Aspects of Graph Packing and Graph Decomposition,” Comput. Sci. Rev. 1 (1), 12–26 (2007).

    Article  MATH  Google Scholar 

Download references