Outputs (9)

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs (2023)
Conference Proceeding
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (57:1-57:15). https://doi.org/10.4230/LIPIcs.MFCS.2023.57

For any finite set H = {H1,. .. , Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,. .. , Hp as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed... Read More about Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.

The Complexity of L(p,q)-Edge-Labelling (2022)
Conference Proceeding
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022). The Complexity of L(p,q)-Edge-Labelling. In P. Mutzel, M. . S. Rahman, & Slamin (Eds.), WALCOM: Algorithms and Computation: 16th International Conference and Workshops, WALCOM 2022, Jember, Indonesia, March 24-26, 2022, Proceedings (175-186). https://doi.org/10.1007/978-3-030-96731-4_15

The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p,q)-Edge-Labelling.

Partitioning H-free graphs of bounded diameter (2021)
Conference Proceeding
Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021). Partitioning H-free graphs of bounded diameter. In H. Ahn, & K. Sadakane (Eds.), . https://doi.org/10.4230/lipics.isaac.2021.21

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ide... Read More about Partitioning H-free graphs of bounded diameter.

Acyclic, star and injective colouring: bounding the diameter (2021)
Conference Proceeding
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2021). Acyclic, star and injective colouring: bounding the diameter. In Ł. Kowalik, M. Pilipczuk, & P. Rzążewski (Eds.), Graph-Theoretic Concepts in Computer Science: 47th International Workshop, WG 2021, Warsaw, Poland, June 23–25, 2021, Revised Selected Papers (336-348). https://doi.org/10.1007/978-3-030-86838-3_26

We examine the effect of bounding the diameter for wellstudied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively.... Read More about Acyclic, star and injective colouring: bounding the diameter.

QCSP on reflexive tournaments (2021)
Conference Proceeding
Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021). QCSP on reflexive tournaments. In P. Mutzel, R. Pagh, & G. Herman (Eds.), . https://doi.org/10.4230/lipics.esa.2021.58

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H1, . . . , Hn so th... Read More about QCSP on reflexive tournaments.

Disjoint paths and connected subgraphs for H-free graphs (2021)
Conference Proceeding
Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2021). Disjoint paths and connected subgraphs for H-free graphs. In P. Flocchini, & L. Moura (Eds.), Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings (414-427). https://doi.org/10.1007/978-3-030-79987-8_29

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint P... Read More about Disjoint paths and connected subgraphs for H-free graphs.

Injective colouring for H-free graphs (2021)
Conference Proceeding
Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2021). Injective colouring for H-free graphs.

A function c : V (G) → {1, 2, . . . , k} is a k-colouring of a graph G if c(u) 6= c(v) whenever u and v are adjacent. If any two colour classes induce the disjoint union of vertices and edges, then c is called injective. Injective colourings are also... Read More about Injective colouring for H-free graphs.

Colouring graphs of bounded diameter in the absence of small cycles (2021)
Conference Proceeding
Martin, B., Paulusma, D., & Smith, S. (2021). Colouring graphs of bounded diameter in the absence of small cycles. In T. Calamoneri, & F. Corò (Eds.), . https://doi.org/10.1007/978-3-030-75242-2_26

For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two non-adjacent vertices u and v. The k-Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is... Read More about Colouring graphs of bounded diameter in the absence of small cycles.

Acyclic, star and injective colouring: a complexity picture for H-free graphs (2020)
Conference Proceeding
Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020). Acyclic, star and injective colouring: a complexity picture for H-free graphs. . https://doi.org/10.4230/lipics.esa.2020.22

A k-colouring c of a graph G is a mapping V(G) → {1,2,… k} such that c(u) ≠ c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. A colouring is acyclic, star, or injective if any two colour classes induce a forest, sta... Read More about Acyclic, star and injective colouring: a complexity picture for H-free graphs.