37 citations · 52 across the 9 of their papers we have counts for
5 papers · 1 filter
Max Point-Tolerance Graphs
Daniele Catanzaro, Steven Chaplick, Stefan Felsner +4
A graph is a \emph{max point-tolerance (MPT)} graph if each vertex of can be mapped to a \emph{pointed-interval} where is an interval of …
Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
Mathew Francis, Pavol Hell, Juraj Stacho
A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that…
4-coloring -free graphs with no induced 5-cycles
Maria Chudnovsky, Peter Maceli, Juraj Stacho +1
We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle and no induced 6-vertex path .
Obstructions to chordal circular-arc graphs of small independence number
Mathew Francis, Pavol Hell, Juraj Stacho
A blocking quadruple (BQ) is a quadruple of vertices of a graph such that any two vertices of the quadruple either miss (have no neighbours on) some path connecting the remaining t…
The vertex leafage of chordal graphs
Steven Chaplick, Juraj Stacho
Every chordal graph can be represented as the intersection graph of a collection of subtrees of a host tree, a so-called {\em tree model} of . The leafage of a con…