Skip to main content

Research Repository

Advanced Search

All Outputs (211)

Obtaining planarity by contracting few edges (2012)
Presentation / Conference Contribution
Golovach, P. A., van 't Hog, P., & Paulusma, D. (2012, December). Obtaining planarity by contracting few edges

The Planar Contraction problem is to test whether a given graph can be made planar by using at most k edge contractions. This problem is known to be NP-complete. We show that it is fixed-parameter tractable when parameterized by k.

Finding vertex-surjective graph homomorphisms (2012)
Presentation / Conference Contribution
Golovach, P. A., Lidicky, B., Martin, B., & Paulusma, D. (2012, December). Finding vertex-surjective graph homomorphisms

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulat... Read More about Finding vertex-surjective graph homomorphisms.

Cerámica española en el extranjero: un caso inglés (2012)
Presentation / Conference Contribution
Gutiérrez, A., & Gelichi, S. (2012). Cerámica española en el extranjero: un caso inglés. In Atti del IX Congresso Internazionale sulla Ceramica Medievale nel Mediterraneo (467-472)

Si bien ciertos tipos de cerámica española fueron exportados regularmente y se hallan frecuentemente distribuidos por todo el Mediterráneo sur, tales importaciones aparecen con menos frecuencia en el norte de Europa. Aquí estos productos importados s... Read More about Cerámica española en el extranjero: un caso inglés.

Closing complexity gaps for coloring problems on H-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & Song, J. (2012, December). Closing complexity gaps for coloring problems on H-free graphs

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V,E) is a mapping c: V → {1,2,…} such that no two adjacent vertices have the same color, i.e., c(u) ≠ c(v) if uv ∈ E; if |c(V)| ≤ k then... Read More about Closing complexity gaps for coloring problems on H-free graphs.

Induced disjoint paths in claw-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012, December). Induced disjoint paths in claw-free graphs

Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i < j ≤ k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a gra...

Induced disjoint paths in AT-free graphs (2012)
Presentation / Conference Contribution
Golovach, P. A., Paulusma, D., & van Leeuwen, E. J. (2012, December). Induced disjoint paths in AT-free graphs

Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i < j ≤ k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a gra...