Korpelainen, Nicholas, Lozin, Vadim V., Malyshev, Dmitriy S. and Tiskin, Alexander. (2011) Boundary properties of graphs for algorithmic graph problems. Theoretical Computer Science, Vol.412 (No.29). pp. 3545-3554. ISSN 0304-3975

Full text not available from this repository.

Abstract

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.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Computer Science Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Computational complexity, Hamiltonian graph theory, Graph theory, Graph coloring
Journal or Publication Title:	Theoretical Computer Science
Publisher:	Elsevier Science BV
ISSN:	0304-3975
Date:	1 July 2011
Volume:	Vol.412
Number:	No.29
Page Range:	pp. 3545-3554
Identification Number:	10.1016/j.tcs.2011.03.001
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	University of Warwick. Centre for Discrete Mathematics and Its Applications (DIMAP), Rossiĭskiĭ fond fundamentalʹnykh issledovaniĭ [Russian Foundation for Basic Research] (RFFI), Gosudarstvennyĭ universitet Vysshai︠a︡ shkola ėkonomiki (Russia) (GU VShĖ), FAP
Grant number:	10-01-00357-a (RFFI), 61.1 (GU VShĖ), 2010-1.3.1-111-017-012 (FAP)
References:	[1] V.E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskret. Math. 4 (2) (1992) 148–157 (in Russian); translation in Discrete Math. Appl. 3 (2) (1993), 191–199. [2] V.E. Alekseev, On lower layers of a lattice of hereditary classes of graphs, Diskretn. Anal. Issled. Oper. Ser. 1 4 (1) (1997) 3–12 (in Russian). [3] V.E. Alekseev, On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Appl. Math. 132 (2003) 17–26. [4] V.E. Alekseev, D.V. Korobitsyn, V.V. Lozin, Boundary classes of graphs for the dominating set problem, Discrete Math. 285 (2004) 1–6. [5] V.E. Alekseev, R. Boliac, D.V. Korobitsyn, V.V. Lozin, NP-hard graph problems and boundary classes of graphs, Theoret. Comput. Sci. 389 (2007) 219–236. [6] E.M. Arkin, J.S.B. Mitchell, V. Polishchuk, Two new classes of hamiltonian graphs (Extended Abstract), Electron. Notes in Discrete Math. 29 (2007) 565–569. [7] József Balogh, Béla Bollobás, David Weinreich, The speed of hereditary properties of graphs, J. Combin. Theory Ser. B 79 (2000) 131–156. [8] H.J. Bandelt, H.M. Mulder, Distance-hereditary graphs, J. Combin. Theory Ser. B 41 (1986) 182–208. [9] R.B. Borie, R.G. Parker, C.A. Tovey, Solving problems on recursively constructed graphs, ACM Comput. Surv. 41 (2008) 1–51. [10] R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philosophical Society, Math. Phys. Sci. 37 (1941) 194–197. [11] M. Chudnovsky, N. Robertson, P.D. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006) 51–229. [12] P.C. Fishburn, An interval graph is not a comparability graph, J. Combin. Theory 8 (1970) 442–443. [13] M.C. Golumbic, U. Rotics, On the clique-width of some perfect graph classes, International J. Foundations of Comput. Sci. 11 (2000) 423–443. [14] A. Itai, C.H. Papadimitriou, J.L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Comput. 11 (1982) 676–686. [15] M. Jean, An interval graph is a comparability graph, J. Combin. Theory 7 (1969) 189–190. [16] N. Korpelainen, V. Lozin, A. Tiskin, Hamiltonian cycles in subcubic graphs: what makes the problem difficult, Lecture Notes in Comput. Sci. 6108 (2010) 320–327. [17] V.V. Lozin, Boundary classes of planar graphs, Combinatorics, Probab. Comput. 17 (2008) 287–295. [18] V. Lozin, D. Rautenbach, Chordal bipartite graphs of bounded tree- and clique-width, Discrete Math. 283 (2004) 151–158. [19] F. Lazebnik, V.A. Ustimenko, A.J. Woldar, A new series of dense graphs of high girth, Bull. AMS 32 (1) (1995) 73–79. [20] D.S. Malyshev, On the number of boundary classes for the vertex 3-colorability problem, Discrete Math. 21 (4) (2009) 129–134 (in Russian). English translation in Discrete Math. Appl. 19(6) (2009) 625–630. [21] D.S. Malyshev, Continual sets of boundary classes of graphs for colorability problems, Discrete Anal. Oper. Res. 16 (5) (2009) 41–51 (in Russian). [22] D.S. Malyshev, On minimal hard classes of graphs, Discrete Anal. Oper. Res. 16 (6) (2009) 43–51 (in Russian). [23] H. Müller, Hamiltonian circuits in chordal bipartite graphs, Discrete Math. 156 (1996) 291–298. [24] O.J. Murphy, Computing independent sets in graphs with large girth, Discrete Appl. Math. 35 (1992) 167–170. [25] S. Norine, P. Seymour, R. Thomas, P. Wollan, Proper minor-closed families are small, J. Combin. Theory Ser. B 96 (2006) 754–757. [26] J. Plesńik, The NP-completeness of the Hamiltonial cycle problem in planar digraphs with degree bound two, Inform. Process. Lett. 8 (1979) 199–201. [27] N. Robertson, P.D. Seymour, Graph minors. V. Excluding a planar graph, J. Combin. Theory Ser. B 41 (1986) 92–114. [28] E.R. Scheinarman, J. Zito, On the size of hereditary classes of graphs, J. Combin. Theory Ser. B 61 (1994) 16–39. [29] J.P. Spinrad, Nonredundant 1’s in Γ -free matrices, SIAM J. Discrete Math. 8 (2) (1995) 251–257.
URI:	http://wrap.warwick.ac.uk/id/eprint/38771

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item