All Outputs (158)

Characterizing graphs of small carving-width (2013)
Journal Article
Belmonte, R., Hof, V. '. P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13-14), 1888-1893. https://doi.org/10.1016/j.dam.2013.02.036

We characterize all graphs that have carving-width at most k for k=1,2,3. In particular, we show that a graph has carving-width at most 3 if and only if it has maximum degree at most 3 and treewidth at most 2. This enables us to identify the immersio... Read More about Characterizing graphs of small carving-width.

Detecting induced minors in AT-free graphs (2013)
Journal Article
Golovach, P., Kratsch, D., & Paulusma, D. (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science, 482, 20-32. https://doi.org/10.1016/j.tcs.2013.02.029

The Induced Minor problem is that of testing whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. If only edge contractions are permitted, we obtain the Contractibility problem. We prove that Induc... Read More about Detecting induced minors in AT-free graphs.

List Coloring in the Absence of a Linear Forest (2013)
Journal Article
Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2015). List Coloring in the Absence of a Linear Forest. Algorithmica, 71(1), 21-35. https://doi.org/10.1007/s00453-013-9777-0

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The Listk-Coloring problem requires in addition that every vertex u must receive a color from some giv... Read More about List Coloring in the Absence of a Linear Forest.

Increasing the minimum degree of a graph by contractions (2013)
Journal Article
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2013). Increasing the minimum degree of a graph by contractions. Theoretical Computer Science, 481, 74-84. https://doi.org/10.1016/j.tcs.2013.02.030

The Degree Contractibility problem is to test whether a given graph G can be modified to a graph of minimum degree at least d by using at most k contractions. We prove the following three results. First, Degree Contractibility is NP-complete even whe... Read More about Increasing the minimum degree of a graph by contractions.

Satisfiability of acyclic and almost acyclic CNF formulas (2013)
Journal Article
Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85-99. https://doi.org/10.1016/j.tcs.2012.12.039

We show that the Satisfiability (SAT) problem for CNF formulas with ββ-acyclic hypergraphs can be solved in polynomial time by using a special type of Davis–Putnam resolution in which each resolvent is a subset of a parent clause. We extend this clas... Read More about Satisfiability of acyclic and almost acyclic CNF formulas.

Three complexity results on coloring Pk-free graphs (2013)
Journal Article
Broersma, H., Fomin, F., Golovach, P., & Paulusma, D. (2013). Three complexity results on coloring Pk-free graphs. European Journal of Combinatorics, 34(3), 609-619. https://doi.org/10.1016/j.ejc.2011.12.008

We prove three complexity results on vertex coloring problems restricted to PkPk-free graphs, i.e., graphs that do not contain a path on kk vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring r... Read More about Three complexity results on coloring Pk-free graphs.

Obtaining planarity by contracting few edges (2013)
Journal Article
Golovach, P., van 't Hof, P., & Paulusma, D. (2013). Obtaining planarity by contracting few edges. Theoretical Computer Science, 476, 38-46. https://doi.org/10.1016/j.tcs.2012.12.041

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

Choosability on H-free graphs (2013)
Journal Article
Golovach, P., Heggernes, P., van 't Hof, P., & Paulusma, D. (2013). Choosability on H-free graphs. Information Processing Letters, 113(4), 107-110. https://doi.org/10.1016/j.ipl.2012.12.003

A graph is H-free if it has no induced subgraph isomorphic to H. We determine the computational complexity of the Choosability problem restricted to H-free graphs for every graph H that does not belong to {K1,3,P1+P2,P1+P3,P4}{K1,3,P1+P2,P1+P3,P4}. W... Read More about Choosability on H-free graphs.

A note on contracting claw-free graphs (2013)
Journal Article
Fiala, J., Kaminski, M., & Paulusma, D. (2013). A note on contracting claw-free graphs. Discrete Mathematics & Theoretical Computer Science, 15(2), 223-232

A graph containment problem is to decide whether one graph called the host graph can be modified into some other graph called the target graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex dele... Read More about A note on contracting claw-free graphs.

4-Coloring H-free graphs when H is small (2013)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2013). 4-Coloring H-free graphs when H is small. Discrete Applied Mathematics, 161(1-2), 140-150. https://doi.org/10.1016/j.dam.2012.08.022

The kk-Coloring problem is to test whether a graph can be colored with at most kk colors such that no two adjacent vertices receive the same color. If a graph GG does not contain a graph HH as an induced subgraph, then GG is called HH-free. For any f... Read More about 4-Coloring H-free graphs when H is small.

Exact algorithms for finding longest cycles in claw-free graphs (2013)
Journal Article
Broersma, H., Fomin, F., Hof van 't, P., & Paulusma, D. (2013). Exact algorithms for finding longest cycles in claw-free graphs. Algorithmica, 65(1), 129 -145. https://doi.org/10.1007/s00453-011-9576-4

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in O*(an)(n) time for some co... Read More about Exact algorithms for finding longest cycles in claw-free graphs.

Detecting induced star-like minors in polynomial time (2012)
Journal Article
Fiala, J., Kaminksi, M., & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of discrete algorithms, 17, 74-85. https://doi.org/10.1016/j.jda.2012.11.002

The Induced Minor problem is to test whether a graph G contains a graph H as an induced minor, i.e., if G can be modified into H by a sequence of vertex deletions and edge contractions. When H is fixed, i.e., not part of the input, this problem is de... Read More about Detecting induced star-like minors in polynomial time.

Computing vertex-surjective homomorphisms to partially reflexive trees (2012)
Journal Article
Golovach, P., Paulusma, D., & Song, J. (2012). Computing vertex-surjective homomorphisms to partially reflexive trees. Theoretical Computer Science, 457, 86-100. https://doi.org/10.1016/j.tcs.2012.06.039

A homomorphism from a graph GG to a graph HH is a vertex mapping f:VG→VHf:VG→VH such that f(u)f(u) and f(v)f(v) form an edge in HH whenever uu and vv form an edge in GG. The HH-Coloring problem is that of testing whether a graph GG allows a homomorph... Read More about Computing vertex-surjective homomorphisms to partially reflexive trees.

Finding vertex-surjective graph homomorphisms (2012)
Journal Article
Golovach, P., Lidicky, B., Martin, B., & Paulusma, D. (2012). Finding vertex-surjective graph homomorphisms. Acta Informatica, 49(6), 381-394. https://doi.org/10.1007/s00236-012-0164-0

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.

On the parameterized complexity of coloring graphs in the absence of a linear forest (2012)
Journal Article
Couturier, J., Golovach, P., Kratsch, D., & Paulusma, D. (2012). On the parameterized complexity of coloring graphs in the absence of a linear forest. Journal of discrete algorithms, 15, 56-62. https://doi.org/10.1016/j.jda.2012.04.008

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The Listk-Coloring problem requires in addition that every vertex u must receive a color from some giv... Read More about On the parameterized complexity of coloring graphs in the absence of a linear forest.

Computing role assignments of proper interval graphs in polynomial time (2012)
Journal Article
Heggernes, P., van 't Hof, P., & Paulusma, D. (2012). Computing role assignments of proper interval graphs in polynomial time. Journal of discrete algorithms, 14, 173-188. https://doi.org/10.1016/j.jda.2011.12.004

An R-role assignment of a graph G is a locally surjective homomorphism from G to graph R. For a fixed graph R, the R-Role Assignment problem is to decide, for an input graph G, whether G has an R-role assignment. When both graphs G and R are given as... Read More about Computing role assignments of proper interval graphs in polynomial time.

On graph contractions and induced minors (2012)
Journal Article
Hof, P. V. '., Kaminski, M., Paulusma, D., Szeider, S., & Thilikos, D. (2012). On graph contractions and induced minors. Discrete Applied Mathematics, 160(6), 799-809. https://doi.org/10.1016/j.dam.2010.05.005

The Induced Minor Containment problem takes as input two graphs G and H, and asks whether G has H as an induced minor. We show that this problem is fixed parameter tractable in |VH| if G belongs to any nontrivial minor-closed graph class and H is a p... Read More about On graph contractions and induced minors.

Distance three labelings of trees (2012)
Journal Article
Fiala, J., Golovach, P., Kratochvil, J., Lidický, B., & Paulusma, D. (2012). Distance three labelings of trees. Discrete Applied Mathematics, 160(6), 764-779. https://doi.org/10.1016/j.dam.2011.02.004

An L(2,1,1)-labeling of a graph G assigns nonnegative integers to the vertices of G in such a way that labels of adjacent vertices differ by at least two, while vertices that are at distance at most three are assigned different labels. The maximum la... Read More about Distance three labelings of trees.

Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time (2012)
Journal Article
Broersma, H., Golovach, P., Paulusma, D., & Song, J. (2012). Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time. Theoretical Computer Science, 423, 1-10. https://doi.org/10.1016/j.tcs.2011.12.076

Let 2P3 denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H-free. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. Its computational comp... Read More about Determining the chromatic number of triangle-free 2P3-free graphs in polynomial time.

Induced packing of odd cycles in planar graphs (2012)
Journal Article
Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2012). Induced packing of odd cycles in planar graphs. Theoretical Computer Science, 420, 28-35. https://doi.org/10.1016/j.tcs.2011.11.004

An induced packing of odd cycles in a graph is a packing such that there is no edge in the graph between any two odd cycles in the packing. We prove that an induced packing of k odd cycles in an n-vertex graph can be found (if it exists) in time 2O(k... Read More about Induced packing of odd cycles in planar graphs.