Page 241 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 241
ALGORITHMIC GRAPH THEORY (MS-54)
ing the specified edge. This provides an algorithm for given one of the objects, finding another.
I have extended Thomason’s algorithm to one which, in a non-eulerian graph, finds a second cy-
cle containing a specified edge and all the odd-degree vertices. I will discuss some other parity
theorems about paths, cycles, and trees in graphs; in particular, attempts to find proofs of them
by showing that the objects of interest are the odd-degree vertices of an associated (generally
large) graph.
Clique-Width: Harnessing the Power of Atoms
Konrad K. Dabrowski, k.k.dabrowski@leeds.ac.uk
University of Leeds, United Kingdom
Coauthors: Tomáš Masaˇrík, Jana Novotná, Daniël Paulusma, Paweł Rzazewski
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded
clique-width. Several of these problems are polynomial-time solvable on a hereditary graph
class G if they are so on the atoms (graphs with no clique cut-set) of G. Hence, we initiate
a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A
graph G is H-free if H is not an induced subgraph of G, and it is (H1, H2)-free if it is both H1-
free and H2-free. A class of H-free graphs has bounded clique-width if and only if its atoms
have this property. This is no longer true for (H1, H2)-free graphs, as evidenced by one known
example. We prove the existence of another such pair (H1, H2) and classify the boundedness of
clique-width on (H1, H2)-free atoms for all but 18 cases.
References
[1] Konrad K. Dabrowski, Tomáš Masaˇrík, Jana Novotná, Daniël Paulusma, and Paweł
Rzazewski. Clique-width: Harnessing the power of atoms. Proc. WG 2020, LNCS,
12301:119–133, 2020. Full version: arXiv:2006.03578.
Colourful components in k-caterpillars and planar graphs
Clément Dallard, clement.dallard@famnit.upr.si
University of Primorska, Slovenia
Coauthor: Janka Chlebíková
A connected component of a vertex-coloured graph is said to be colourful if all its vertices
have different colours. By extension, a graph is colourful if all its connected components are
colourful. Given a vertex-coloured graph and an integer p, the COLOURFUL COMPONENTS
problem asks whether there exist at most p edges whose removal makes the graph colourful.
Bulteau, Dabrowski, Fertin, Johnson, Paulusma, and Vialette (2019) proved that COLOURFUL
COMPONENTS is NP-complete on trees with maximum degree at most 6 and asked whether the
same would hold if the maximum degree is at most 5. We show that the problem remains NP-
complete on binary 4-caterpillars, ternary 3-caterpillars and quaternary 2-caterpillars, where a
k-caterpillar is a tree containing a path P such that every vertex is at distance at most k from P .
On the other hand, we provide a linear-time algorithm for 1-caterpillars (without restriction on
the maximum degree), and thus almost settle the complexity dichotomy on k-caterpillars with
respect to the maximum degree. COLOURFUL COMPONENTS has also been studied in vertex-
239
ing the specified edge. This provides an algorithm for given one of the objects, finding another.
I have extended Thomason’s algorithm to one which, in a non-eulerian graph, finds a second cy-
cle containing a specified edge and all the odd-degree vertices. I will discuss some other parity
theorems about paths, cycles, and trees in graphs; in particular, attempts to find proofs of them
by showing that the objects of interest are the odd-degree vertices of an associated (generally
large) graph.
Clique-Width: Harnessing the Power of Atoms
Konrad K. Dabrowski, k.k.dabrowski@leeds.ac.uk
University of Leeds, United Kingdom
Coauthors: Tomáš Masaˇrík, Jana Novotná, Daniël Paulusma, Paweł Rzazewski
Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded
clique-width. Several of these problems are polynomial-time solvable on a hereditary graph
class G if they are so on the atoms (graphs with no clique cut-set) of G. Hence, we initiate
a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A
graph G is H-free if H is not an induced subgraph of G, and it is (H1, H2)-free if it is both H1-
free and H2-free. A class of H-free graphs has bounded clique-width if and only if its atoms
have this property. This is no longer true for (H1, H2)-free graphs, as evidenced by one known
example. We prove the existence of another such pair (H1, H2) and classify the boundedness of
clique-width on (H1, H2)-free atoms for all but 18 cases.
References
[1] Konrad K. Dabrowski, Tomáš Masaˇrík, Jana Novotná, Daniël Paulusma, and Paweł
Rzazewski. Clique-width: Harnessing the power of atoms. Proc. WG 2020, LNCS,
12301:119–133, 2020. Full version: arXiv:2006.03578.
Colourful components in k-caterpillars and planar graphs
Clément Dallard, clement.dallard@famnit.upr.si
University of Primorska, Slovenia
Coauthor: Janka Chlebíková
A connected component of a vertex-coloured graph is said to be colourful if all its vertices
have different colours. By extension, a graph is colourful if all its connected components are
colourful. Given a vertex-coloured graph and an integer p, the COLOURFUL COMPONENTS
problem asks whether there exist at most p edges whose removal makes the graph colourful.
Bulteau, Dabrowski, Fertin, Johnson, Paulusma, and Vialette (2019) proved that COLOURFUL
COMPONENTS is NP-complete on trees with maximum degree at most 6 and asked whether the
same would hold if the maximum degree is at most 5. We show that the problem remains NP-
complete on binary 4-caterpillars, ternary 3-caterpillars and quaternary 2-caterpillars, where a
k-caterpillar is a tree containing a path P such that every vertex is at distance at most k from P .
On the other hand, we provide a linear-time algorithm for 1-caterpillars (without restriction on
the maximum degree), and thus almost settle the complexity dichotomy on k-caterpillars with
respect to the maximum degree. COLOURFUL COMPONENTS has also been studied in vertex-
239
