Abstract
We consider the following problem: can a certain graph parameter of some given graph G be reduced by at least d, for some integer d, via at most k graph operations from some specified set S, for some given integer k? As graph parameters we take the chromatic number and the clique number. We let the set S consist of either an edge contraction or a vertex deletion. As all these problems are NP-complete for general graphs even if d is fixed, we restrict the input graph G to some special graph class. We continue a line of research that considers these problems for subclasses of perfect graphs, but our main results are full classifications, from a computational complexity point of view, for graph classes characterized by forbidding a single induced connected subgraph H.
D. Paulusma—Author supported by EPSRC (EP/K025090/1).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We can modify the gadgets for proving NP-completeness for the case \(d=1\) in a straightforward way to obtain NP-completeness for every constant \(d\ge 2\). A similar remark holds for other theorems. Details will be given in the journal version.
References
Bazgan, C., Bentz, C., Picouleau, C., Ries, B.: Blockers for the stability number and the chromatic number. Graphs Comb. 31, 73–90 (2015)
Bazgan, C., Toubaline, S., Tuza, Z.: Complexity of most vital nodes for independent set in graphs related to tree structures. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol. 6460, pp. 154–166. Springer, Heidelberg (2011)
Bazgan, C., Toubaline, S., Tuza, Z.: The most vital nodes with respect to independent set and vertex cover. Discrete Appl. Math. 159, 1933–1946 (2011)
Bentz, C., Costa, M.-C., de Werra, D., Picouleau, C., Ries, B.: Weighted Transversals and blockers for some optimization problems in graphs. In: Progress in Combinatorial Optimization. ISTE-WILEY (2012)
Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006)
Costa, M.-C., de Werra, D., Picouleau, C.: Minimum \(d\)-blockers and \(d\)-transversals in graphs. J. Comb. Optim. 22, 857–872 (2011)
Diner, Ö.Y., Paulusma, D., Picouleau, C., Ries, B.: Contraction blockers for graphs with forbidden induced paths. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 194–207. Springer, Heidelberg (2015)
Földes, S., Hammer, P.L.: Split graphs. Congressus Numerantium 19, 311–315 (1977). 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Král’, D., Kratochvíl, J., Tuza, Z., Woeginger, G.J.: Complexity of coloring graphs without forbidden induced subgraphs. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 254–262. Springer, Heidelberg (2001)
Maffray, F., Preissmann, M.: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs. Discrete Math. 162, 313–317 (1996)
Olariu, S.: Paw-free graphs. Inf. Process. Lett. 28, 53–54 (1988)
Pajouh, F.M., Boginski, V., Pasiliao, E.L.: Minimum vertex blocker clique problem. Networks 64, 48–64 (2014)
Poljak, S.: A note on the stable sets and coloring of graphs. Comment. Math. Univ. Carolin. 15, 307–309 (1974)
Ries, B., Bentz, C., Picouleau, C., de Werra, D., Costa, M.-C., Zenklusen, R.: Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid. Discrete Math. 310, 132–146 (2010)
Toubaline, S.: Détermination des éléments les plus vitaux pour des problèmes de graphes. Ph.D. Thesis, Université Paris-Dauphine (2010)
West, D.B.: Introduction to Graph Theory. Prentice-Hall, Upper Saddle River (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Paulusma, D., Picouleau, C., Ries, B. (2016). Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions. In: Cerulli, R., Fujishige, S., Mahjoub, A. (eds) Combinatorial Optimization. ISCO 2016. Lecture Notes in Computer Science(), vol 9849. Springer, Cham. https://doi.org/10.1007/978-3-319-45587-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-45587-7_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45586-0
Online ISBN: 978-3-319-45587-7
eBook Packages: Computer ScienceComputer Science (R0)