Page 246 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 246
ALGORITHMIC GRAPH THEORY (MS-54)
COLORING problem is open for this class. The time complexity of VERTEX COLORING is also
open for graphs of stability number at most three. In this talk, we consider the intersection
of these two classes: even-hole-free graphs of stability number at most three, or equivalently,
(4K1, C4, C6)-free graphs. We show that such graphs can be recognized and colored in cubic
time.
Circularly compatible ones, D-circularity, and proper circular-arc
bigraphs
Martín Safe, msafe@uns.edu.ar
Departamento de Matemática, Universidad Nacional del Sur, Argentina
In 1969, Alan Tucker characterized proper circular-arc graphs as those graphs whose augmented
adjacency matrices have the circularly compatible ones property. Moreover, he also found a
polynomial-time algorithm for deciding whether any given augmented adjacency matrix has the
circularly compatible ones property. These results allowed him to devise the first polynomial-
time recognition algorithm for proper circular-arc graphs. However, as Tucker himself remarks,
he did not solve the problems of finding a structure theorem and an efficient recognition al-
gorithm for the circularly compatible ones property in arbitrary matrices (i.e., not restricted to
augmented adjacency matrices only). In this work, we solve these problems. More precisely, we
give a minimal forbidden submatrix characterization for the circularly compatible ones property
in arbitrary matrices and a linear-time recognition algorithm for the same property. We derive
these results from analogous ones for the related D-circular property. Interestingly, these results
lead to a minimal forbidden induced subgraph characterization and a linear-time recognition al-
gorithm for proper circular-arc bigraphs, solving a problem first posed by Basu, Das, Ghosh,
and Sen [J. Graph Theory, 73(4):361–376, 2013]. Our findings generalize some known results
about D-interval hypergraphs and proper interval bigraphs.
On the treewidth of even-hole-free graphs
Ni Luh Dewi Sintiari, ni-luh-dewi.sintiari@ens-lyon.fr
ENS de Lyon, France
Even-hole-free graphs attracted attention lately (see [1]). However, many questions about them
remain unanswered: polytime algorithm to color them, or to find a maximum stable set, despite
the existence of several decomposition theorems. In general, the class of all even-hole-free
graphs has unbounded tree-width, as it contains all complete graphs. Nonetheless, bounding
the size of the maximum clique does not turn the class into having bounded treewidth, because
there exists a family of even-hole-free graphs with no 4-vertex clique which has unbounded
tree-width [2]. We observe that the graph constructed in [2] has unbounded degree and contains
arbitrarily large clique-minors. We ask whether this is necessary.
We prove that for every graph G, if G excludes a fixed graph H as a minor, then G either has
small tree-width, or G contains a large wall or the line graph of a large wall as induced subgraph.
This can be seen as a strengthening of Robertson and Seymour’s excluded grid theorem for
the case of minor-free graphs. Our theorem implies that every class of even-hole-free graphs
excluding a fixed graph as a minor has bounded tree-width. In fact, our theorem applies to a
more general class: (theta, prism)-free graphs. Furthermore, we conjecture that even-hole-free
244
COLORING problem is open for this class. The time complexity of VERTEX COLORING is also
open for graphs of stability number at most three. In this talk, we consider the intersection
of these two classes: even-hole-free graphs of stability number at most three, or equivalently,
(4K1, C4, C6)-free graphs. We show that such graphs can be recognized and colored in cubic
time.
Circularly compatible ones, D-circularity, and proper circular-arc
bigraphs
Martín Safe, msafe@uns.edu.ar
Departamento de Matemática, Universidad Nacional del Sur, Argentina
In 1969, Alan Tucker characterized proper circular-arc graphs as those graphs whose augmented
adjacency matrices have the circularly compatible ones property. Moreover, he also found a
polynomial-time algorithm for deciding whether any given augmented adjacency matrix has the
circularly compatible ones property. These results allowed him to devise the first polynomial-
time recognition algorithm for proper circular-arc graphs. However, as Tucker himself remarks,
he did not solve the problems of finding a structure theorem and an efficient recognition al-
gorithm for the circularly compatible ones property in arbitrary matrices (i.e., not restricted to
augmented adjacency matrices only). In this work, we solve these problems. More precisely, we
give a minimal forbidden submatrix characterization for the circularly compatible ones property
in arbitrary matrices and a linear-time recognition algorithm for the same property. We derive
these results from analogous ones for the related D-circular property. Interestingly, these results
lead to a minimal forbidden induced subgraph characterization and a linear-time recognition al-
gorithm for proper circular-arc bigraphs, solving a problem first posed by Basu, Das, Ghosh,
and Sen [J. Graph Theory, 73(4):361–376, 2013]. Our findings generalize some known results
about D-interval hypergraphs and proper interval bigraphs.
On the treewidth of even-hole-free graphs
Ni Luh Dewi Sintiari, ni-luh-dewi.sintiari@ens-lyon.fr
ENS de Lyon, France
Even-hole-free graphs attracted attention lately (see [1]). However, many questions about them
remain unanswered: polytime algorithm to color them, or to find a maximum stable set, despite
the existence of several decomposition theorems. In general, the class of all even-hole-free
graphs has unbounded tree-width, as it contains all complete graphs. Nonetheless, bounding
the size of the maximum clique does not turn the class into having bounded treewidth, because
there exists a family of even-hole-free graphs with no 4-vertex clique which has unbounded
tree-width [2]. We observe that the graph constructed in [2] has unbounded degree and contains
arbitrarily large clique-minors. We ask whether this is necessary.
We prove that for every graph G, if G excludes a fixed graph H as a minor, then G either has
small tree-width, or G contains a large wall or the line graph of a large wall as induced subgraph.
This can be seen as a strengthening of Robertson and Seymour’s excluded grid theorem for
the case of minor-free graphs. Our theorem implies that every class of even-hole-free graphs
excluding a fixed graph as a minor has bounded tree-width. In fact, our theorem applies to a
more general class: (theta, prism)-free graphs. Furthermore, we conjecture that even-hole-free
244
