Showing cs.DMShow all
3 papers · 1 filter
cs.DM2026
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
Jan Bok, Nikola Jedlickova, Barnaby Martin +3
A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. Hence, every injec…
cs.DM2025
Bounding Width on Graph Classes of Constant Diameter
Konrad K. Dabrowski, Tala Eagling-Vose, Noleen Köhler +2
We determine if the width of a graph class changes from unbounded to bounded if we consider only those graphs from whose diameter is bounded. As parameters we…
cs.DM2024
Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs
Vadim Lozin, Barnaby Martin, Sukanya Pandey +4
For a fixed set of graphs, a graph is -subgraph-free if does not contain any as a (not necessarily induced) subgraph. A recently propo…