×

zbMATH — the first resource for mathematics

Boundary properties of graphs for algorithmic graph problems. (English) Zbl 1222.05243
Summary: The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle and vertex \(k\)-colorability. In particular, we discover the first two boundary classes for the Hamiltonian cycle problem and prove that for any \(k>3\) there is a continuum of boundary classes for vertex \(k\)-colorability.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
05C45 Eulerian and Hamiltonian graphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alekseev, V.E., Range of values of entropy of hereditary classes of graphs, Diskret. math., 4, 2, 148-157, (1992), (in Russian); translation in Discrete Math. Appl. 3 (2) (1993), 191-199 · Zbl 0766.05088
[2] Alekseev, V.E., On lower layers of a lattice of hereditary classes of graphs, Diskretn. anal. issled. oper. ser. 1, 4, 1, 3-12, (1997), (in Russian) · Zbl 0880.05051
[3] Alekseev, V.E., On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete appl. math., 132, 17-26, (2003) · Zbl 1029.05140
[4] Alekseev, V.E.; Korobitsyn, D.V.; Lozin, V.V., Boundary classes of graphs for the dominating set problem, Discrete math., 285, 1-6, (2004) · Zbl 1121.05081
[5] Alekseev, V.E.; Boliac, R.; Korobitsyn, D.V.; Lozin, V.V., NP-hard graph problems and boundary classes of graphs, Theoret. comput. sci., 389, 219-236, (2007) · Zbl 1143.68058
[6] Arkin, E.M.; Mitchell, J.S.B.; Polishchuk, V., Two new classes of Hamiltonian graphs (extended abstract), Electron. notes in discrete math., 29, 565-569, (2007) · Zbl 1341.05140
[7] Balogh, József; Bollobás, Béla; Weinreich, David, The speed of hereditary properties of graphs, J. combin. theory ser. B, 79, 131-156, (2000) · Zbl 1026.05062
[8] Bandelt, H.J.; Mulder, H.M., Distance-hereditary graphs, J. combin. theory ser. B, 41, 182-208, (1986) · Zbl 0605.05024
[9] Borie, R.B.; Parker, R.G.; Tovey, C.A., Solving problems on recursively constructed graphs, ACM comput. surv., 41, 1-51, (2008)
[10] Brooks, R.L., On colouring the nodes of a network, Proc. Cambridge philosophical society, math. phys. sci., 37, 194-197, (1941) · Zbl 0027.26403
[11] Chudnovsky, M.; Robertson, N.; Seymour, P.D.; Thomas, R., The strong perfect graph theorem, Ann. math., 164, 51-229, (2006) · Zbl 1112.05042
[12] Fishburn, P.C., An interval graph is not a comparability graph, J. combin. theory, 8, 442-443, (1970) · Zbl 0183.28602
[13] Golumbic, M.C.; Rotics, U., On the clique-width of some perfect graph classes, International J. foundations of comput. sci., 11, 423-443, (2000) · Zbl 1320.05090
[14] Itai, A.; Papadimitriou, C.H.; Szwarcfiter, J.L., Hamilton paths in grid graphs, SIAM J. comput., 11, 676-686, (1982) · Zbl 0506.05043
[15] Jean, M., An interval graph is a comparability graph, J. combin. theory, 7, 189-190, (1969) · Zbl 0183.28603
[16] Korpelainen, N.; Lozin, V.; Tiskin, A., Hamiltonian cycles in subcubic graphs: what makes the problem difficult, Lecture notes in comput. sci., 6108, 320-327, (2010) · Zbl 1284.68300
[17] Lozin, V.V., Boundary classes of planar graphs, Combinatorics, probab. comput., 17, 287-295, (2008) · Zbl 1166.05016
[18] Lozin, V.; Rautenbach, D., Chordal bipartite graphs of bounded tree- and clique-width, Discrete math., 283, 151-158, (2004) · Zbl 1044.05060
[19] Lazebnik, F.; Ustimenko, V.A.; Woldar, A.J., A new series of dense graphs of high girth, Bull. AMS, 32, 1, 73-79, (1995) · Zbl 0822.05039
[20] Malyshev, D.S., On the number of boundary classes for the vertex 3-colorability problem, Discrete math., 21, 4, 129-134, (2009), (in Russian). English translation in Discrete Math. Appl. 19(6) (2009) 625-630
[21] Malyshev, D.S., Continual sets of boundary classes of graphs for colorability problems, Discrete anal. oper. res., 16, 5, 41-51, (2009), (in Russian) · Zbl 1249.05130
[22] Malyshev, D.S., On minimal hard classes of graphs, Discrete anal. oper. res., 16, 6, 43-51, (2009), (in Russian) · Zbl 1249.05368
[23] Müller, H., Hamiltonian circuits in chordal bipartite graphs, Discrete math., 156, 291-298, (1996) · Zbl 0856.68113
[24] Murphy, O.J., Computing independent sets in graphs with large girth, Discrete appl. math., 35, 167-170, (1992) · Zbl 0769.05053
[25] Norine, S.; Seymour, P.; Thomas, R.; Wollan, P., Proper minor-closed families are small, J. combin. theory ser. B, 96, 754-757, (2006) · Zbl 1093.05065
[26] Plesńik, J., The NP-completeness of the hamiltonial cycle problem in planar digraphs with degree bound two, Inform. process. lett., 8, 199-201, (1979) · Zbl 0399.68070
[27] Robertson, N.; Seymour, P.D., Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[28] Scheinarman, E.R.; Zito, J., On the size of hereditary classes of graphs, J. combin. theory ser. B, 61, 16-39, (1994) · Zbl 0811.05048
[29] Spinrad, J.P., Nonredundant 1’s in \(\Gamma\)-free matrices, SIAM J. discrete math., 8, 2, 251-257, (1995) · Zbl 0837.05028
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.