Page 242 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 242
ALGORITHMIC GRAPH THEORY (MS-54)
coloured graphs with a bounded number of colours. Bruckner, Hüffner, Komusiewicz, Nie-
dermeier, Thiel, and Uhlmann (2012) showed that the problem is NP-complete on 3-coloured
graphs with maximum degree 6, and Bulteau et al. asked whether the problem would remain
NP-complete on graphs with bounded number of colors and maximum degree 3. We answer
their question in the affirmative by showing that the problem is NP-complete on 5-coloured pla-
nar graphs with maximum degree 4 and on 12-coloured planar graphs with maximum degree 3.
Firebreaking and Firefighting
Jess Enright, jessica.enright@glasgow.ac.uk
University of Glasgow, United Kingdom
Coauthors: Kathleen D. Barnetson, Jared Howell, David A. Pike, Brady Ryan,
Andrea C. Burgess
In the classic firefighter game, a fire burns and firefighters defend in turns. Motivated by a
practical epidemiological question, we defined a one-shot version of this game, and plan to
discuss both some new progress on firefighting and this one-shot version: the FIREBREAK
problem.
Suppose we have a network that is represented by a graph G. Potentially a fire (or other
type of contagion) might erupt at some vertex of G. We are able to respond to this outbreak
by establishing a firebreak at k other vertices of G, so that the fire cannot pass through these.
fortified vertices. The question that now arises is which k vertices will result in the greatest
number of vertices being saved from the fire, assuming that the fire will spread to every vertex
that is not fully behind the k vertices of the firebreak. This is the essence of the FIREBREAK
decision problem, which is the focus of this talk. We establish that the problem is intractable on
the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear
time when restricted to graphs having constant-bounded treewidth, or in polynomial time when
restricted to convenient classes of intersection graphs.
Graphs with two moplexes are more than perfect
Meike Hatzel, meike.hatzel@tu-berlin.de
TU Berlin, Germany
Coauthors: Robert Ganian, Matjaž Krnc, Clément Dallard, Martin Milanicˇ
A well-known result by Dirac (1961) states that every chordal graph contains a simplicial vertex.
This theorem proved to be very useful for structural and algorithmic applications. Moplexes are
a generalisation of simplicial vertices in chordal graphs to the setting of general graphs, as Berry
and Bordat (1998) proved that every non-complete graph contains at least two moplexes.
There are results on the structure of chordal graphs with a bounded number of simplicial
modules, for example the chordal graphs having at most two simplicial modules are interval.
This motivates the research of graphs with a bounded number of moplexes. As only complete
graphs have exactly one moplex, we consider the smallest interesting case: the class of graphs
with at most two moplexes. Berry and Bordat (2001) proved that this class of graphs contains all
connected proper interval graphs and is contained in the class of AT-free graphs. We strengthen
the latter inclusion in two ways. First, we generalise it by proving that the asteroidal number
240
coloured graphs with a bounded number of colours. Bruckner, Hüffner, Komusiewicz, Nie-
dermeier, Thiel, and Uhlmann (2012) showed that the problem is NP-complete on 3-coloured
graphs with maximum degree 6, and Bulteau et al. asked whether the problem would remain
NP-complete on graphs with bounded number of colors and maximum degree 3. We answer
their question in the affirmative by showing that the problem is NP-complete on 5-coloured pla-
nar graphs with maximum degree 4 and on 12-coloured planar graphs with maximum degree 3.
Firebreaking and Firefighting
Jess Enright, jessica.enright@glasgow.ac.uk
University of Glasgow, United Kingdom
Coauthors: Kathleen D. Barnetson, Jared Howell, David A. Pike, Brady Ryan,
Andrea C. Burgess
In the classic firefighter game, a fire burns and firefighters defend in turns. Motivated by a
practical epidemiological question, we defined a one-shot version of this game, and plan to
discuss both some new progress on firefighting and this one-shot version: the FIREBREAK
problem.
Suppose we have a network that is represented by a graph G. Potentially a fire (or other
type of contagion) might erupt at some vertex of G. We are able to respond to this outbreak
by establishing a firebreak at k other vertices of G, so that the fire cannot pass through these.
fortified vertices. The question that now arises is which k vertices will result in the greatest
number of vertices being saved from the fire, assuming that the fire will spread to every vertex
that is not fully behind the k vertices of the firebreak. This is the essence of the FIREBREAK
decision problem, which is the focus of this talk. We establish that the problem is intractable on
the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear
time when restricted to graphs having constant-bounded treewidth, or in polynomial time when
restricted to convenient classes of intersection graphs.
Graphs with two moplexes are more than perfect
Meike Hatzel, meike.hatzel@tu-berlin.de
TU Berlin, Germany
Coauthors: Robert Ganian, Matjaž Krnc, Clément Dallard, Martin Milanicˇ
A well-known result by Dirac (1961) states that every chordal graph contains a simplicial vertex.
This theorem proved to be very useful for structural and algorithmic applications. Moplexes are
a generalisation of simplicial vertices in chordal graphs to the setting of general graphs, as Berry
and Bordat (1998) proved that every non-complete graph contains at least two moplexes.
There are results on the structure of chordal graphs with a bounded number of simplicial
modules, for example the chordal graphs having at most two simplicial modules are interval.
This motivates the research of graphs with a bounded number of moplexes. As only complete
graphs have exactly one moplex, we consider the smallest interesting case: the class of graphs
with at most two moplexes. Berry and Bordat (2001) proved that this class of graphs contains all
connected proper interval graphs and is contained in the class of AT-free graphs. We strengthen
the latter inclusion in two ways. First, we generalise it by proving that the asteroidal number
240
