Buscar
Mostrando ítems 1-10 de 62
Balancedness of subclasses of circular-arc graphs
(Discrete Mathematics and Theoretical Computer Science, 2014-03)
A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, ...
Normal Helly circular-arc graphs and its subclasses
(Elsevier Science, 2013-05)
A Helly circular-arc model M=(C,A) is a circle C together with a Helly family A of arcs of C. If no arc is contained in any other, then M is a proper Helly circular-arc model, if every arc has the same length, then M is a ...
Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
(Elsevier Science, 2014-02)
Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous ...
The clique operator on circular-arc graphs
(Elsevier Science, 2010-06)
A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is ...
Balancedness of some subclasses of circular-arc graphs
(Elsevier Science, 2010-08)
A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs ...
On the bend number of circular-arc graphs as edge intersection graphs of paths on a grid
(Elsevier B.V., 2018)
Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge
intersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertex
of the graph a nontrivial path on a ...
Essential obstacles to Helly circular-arc graphs
(Elsevier Science, 2022-10-30)
A Helly circular-arc graph is the intersection graph of a set of arcs on a circle having the Helly property. We introduce essential obstacles, which are a refinement of the notion of obstacles, and prove that essential ...