Page 247 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 247
ALGORITHMIC GRAPH THEORY (MS-54)
graphs of bounded degree have bounded tree-width, and we prove it for subcubic graphs and
give a partial result when the maximum degree is four. This conjecture is now proved in [3].
Based on a joint work with Pierre Aboulker, Isolde Adler, Eun Jung Kim, and Nicolas
Trotignon.
References
[1] K. Vuškovic´. Even-hole-free graphs: a survey. Applicable Analysis and Discrete Mathe-
matics, 2010.
[2] N. L. D. Sintiari and N. Trotignon. (Theta, triangle)-free and (even hole, K4)-free
graphs. Part 1: Layered wheels. Journal of Graph Theory (early view), 2021.
[3] T. Abrishami, M. Chudnovsky, K. Vuškovic´. Even-hole-free graphs with bounded degree
have bounded treewidth. arXiv 2009.01297, 2020.
On 12-regular nut graphs
Riste Škrekovski, skrekovski@gmail.com
FMF-UL & FIŠ, Slovenia
Coauthors: Nino Bašic´, Martin Knor
A nut graph is a simple graph whose adjacency matrix is singular with 1-dimensional kernel
and corresponding eigenvector with non-zero elements. For each d ∈ {3, 4, . . . , 11} are known
all values n for which there exists a d-regular nut graph of order n. In the talk, we consider all
values n for which there exists a 12-regular nut graph of order n.
Treewidth versus clique number: a complete dichotomy for one forbidden
structure
Kenny Štorgel, kennystorgel.research@gmail.com
Faculty of Information studies in Novo mesto, Slovenia
Coauthors: Clément Dallard, Martin Milanicˇ
Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons.
A necessary condition for a graph class to have bounded treewidth is the absence of large
cliques. We study graph classes closed under taking induced subgraphs in which this condi-
tion is also sufficient, which we call (tw, ω)-bounded. For six graph containment relations (the
subgraph, topological minor, and minor relations, as well as their induced variants) we give a
complete characterization of graphs H for which the class of graphs excluding H is (tw, ω)-
bounded.
Our results yield an infinite family of χ-bounded induced-minor-closed graph classes and
imply that the class of 1-perfectly orientable graphs is (tw, ω)-bounded, leading to linear-time
algorithms for k-coloring 1-perfectly orientable graphs for every fixed k. This answers a ques-
tion of Brešar, Hartinger, Kos, and Milanicˇ (2018) and one of Beisegel, Chudnovsky, Gurvich,
Milanicˇ, and Servatius (2019), respectively. We also reveal some further algorithmic implica-
tions of (tw, ω)-boundedness related to list k-coloring and clique problems.
245
graphs of bounded degree have bounded tree-width, and we prove it for subcubic graphs and
give a partial result when the maximum degree is four. This conjecture is now proved in [3].
Based on a joint work with Pierre Aboulker, Isolde Adler, Eun Jung Kim, and Nicolas
Trotignon.
References
[1] K. Vuškovic´. Even-hole-free graphs: a survey. Applicable Analysis and Discrete Mathe-
matics, 2010.
[2] N. L. D. Sintiari and N. Trotignon. (Theta, triangle)-free and (even hole, K4)-free
graphs. Part 1: Layered wheels. Journal of Graph Theory (early view), 2021.
[3] T. Abrishami, M. Chudnovsky, K. Vuškovic´. Even-hole-free graphs with bounded degree
have bounded treewidth. arXiv 2009.01297, 2020.
On 12-regular nut graphs
Riste Škrekovski, skrekovski@gmail.com
FMF-UL & FIŠ, Slovenia
Coauthors: Nino Bašic´, Martin Knor
A nut graph is a simple graph whose adjacency matrix is singular with 1-dimensional kernel
and corresponding eigenvector with non-zero elements. For each d ∈ {3, 4, . . . , 11} are known
all values n for which there exists a d-regular nut graph of order n. In the talk, we consider all
values n for which there exists a 12-regular nut graph of order n.
Treewidth versus clique number: a complete dichotomy for one forbidden
structure
Kenny Štorgel, kennystorgel.research@gmail.com
Faculty of Information studies in Novo mesto, Slovenia
Coauthors: Clément Dallard, Martin Milanicˇ
Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons.
A necessary condition for a graph class to have bounded treewidth is the absence of large
cliques. We study graph classes closed under taking induced subgraphs in which this condi-
tion is also sufficient, which we call (tw, ω)-bounded. For six graph containment relations (the
subgraph, topological minor, and minor relations, as well as their induced variants) we give a
complete characterization of graphs H for which the class of graphs excluding H is (tw, ω)-
bounded.
Our results yield an infinite family of χ-bounded induced-minor-closed graph classes and
imply that the class of 1-perfectly orientable graphs is (tw, ω)-bounded, leading to linear-time
algorithms for k-coloring 1-perfectly orientable graphs for every fixed k. This answers a ques-
tion of Brešar, Hartinger, Kos, and Milanicˇ (2018) and one of Beisegel, Chudnovsky, Gurvich,
Milanicˇ, and Servatius (2019), respectively. We also reveal some further algorithmic implica-
tions of (tw, ω)-boundedness related to list k-coloring and clique problems.
245
