# The Library

### Boundary properties of graphs for algorithmic graph problems

Tools

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

Official URL: http://dx.doi.org/10.1016/j.tcs.2011.03.001

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

[error in script] [error in script]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

### Actions (login required)

View Item |