Robert Brignall

dblp:00/4463 · DBLP profile ↗
← Back
5ranked-venue papers
4as first author
2since 2021 · last 2023
0000-0002-2769-4853ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 5 · 4 first-author · 2 since 2021
YearPublicationVenuePosition
2023 A Framework for Minimal Hereditary Classes of Graphs of Unbounded Clique-Width
abstract
Abstract. We create a framework for hereditary graph classes [Formula: see text] built on a two-dimensional grid of vertices and edge sets defined by a triple [Formula: see text] of objects that define edges between consecutive columns, edges between nonconsecutive columns (called bonds), and edges within columns. This framework captures a large family of minimal hereditary classes of graphs of unbounded clique-width, some previously identified and many new ones, although we do not claim this includes all such classes. We show that a graph class [Formula: see text] has unbounded clique-width if and only if a certain parameter [Formula: see text] is unbounded. We further show that [Formula: see text] is minimal of unbounded clique-width (and, indeed, minimal of unbounded linear clique-width) if another parameter [Formula: see text] is bounded, and also [Formula: see text] has defined recurrence characteristics. Both the parameters [Formula: see text] and [Formula: see text] are properties of a triple [Formula: see text] and measure the number of distinct neighborhoods in certain auxiliary graphs. Throughout our work, we introduce new methods to the study of clique-width, including the use of Ramsey theory in arguments related to unboundedness, and explicit (linear) clique-width expressions for subclasses of minimal classes of unbounded clique-width.
Robert Brignall, Daniel Cocks
SIAM J. Discret. Math.1
2021 Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
Aistis Atminas, Robert Brignall, Vadim V. Lozin, Juraj Stacho
Discret. Appl. Math.2
2019 Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs
Robert Brignall, Ho-Jin Choi, Jisu Jeong, Sang-il Oum
Discret. Appl. Math.1
2016 Bichain graphs: Geometric model and universal graphs
Robert Brignall, Vadim V. Lozin, Juraj Stacho
Discret. Appl. Math.1
2008 Simple permutations: Decidability and unavoidable substructures
Robert Brignall, Nikola Ruskuc, Vincent Vatter
Theor. Comput. Sci.1