Results on Circular-Arc Bigraphs

• Fabricio Schiavon Kolberg UFPA
• Marina Groshaus Universitad de Buenos Aires
• André Luiz Pires Guedes UFPA
• Renato Carmo UFPA

DOI: https://doi.org/10.5753/etc.2016.9846

Resumo

We present a series of results related to the structural properties of the bipartite graph class known as circular-arc bigraphs. We also propose the definition of a Helly circular-arc bigraph subclass, based on a concept known as bipartite-Helly, along with a few results related to its structural properties.

 

Referências

Basu, A., Das, S., Ghosh, S., and Sen, M. (2013). Circular-arc bigraphs and its subclasses. Journal of Graph Theory, 73(4):361–376.

Das, A. K. and Chakraborty, R. (2015). Algorithms and Discrete Applied Mathematics: First International Conference, CALDAM 2015, Kanpur, India, February 8-10, 2015. Proceedings, chapter New Characterizations of Proper Interval Bigraphs and Proper Circular Arc Bigraphs, pages 117–125. Springer International Publishing, Cham.

Francis, M. C., Hell, P., and Stacho, J. (2014). Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm. CoRR, abs/1408.2639.

Groshaus, M. and Szwarcfiter, J. (2007). Biclique-helly graphs. Graphs and Combinatorics, 23:633 – 645.

Groshaus, M. and Szwarcfiter, J. (2008). On hereditary helly classes of graphs. Discrete Mathematics & Theoretical Computer Science, 10(1).

Groshaus, M. and Szwarcfiter, J. L. (2010). Biclique graphs and biclique matrices. Journal of Graph Theory, 63(1):1–16.

Hell, P. and Huang, J. (2004). Interval bigraphs and circular arc graphs. J. Graph Theory, 46:313–327.

Helly, E. (1923). U¨ berMengen konvexer Ko¨ rper mit gemeinschaftlichen Punkten. Jahresber. Dtsch. Math.-Ver., 32:175–176.

Lin, M. C. and Szwarcfiter, J. L. (2009). Characterizations and recognition of circular-arc graphs and subclasses: A survey. Discrete Mathematics, 309(18):5618–5635. Combinatorics 2006, A Meeting in Celebration of Pavol Hell’s 60th Birthday (May 1-5,2006).

McConnell, R. M. (2003). Linear-time recognition of circular-arc graphs. Algorithmica, 37(2):93–147.

Soulignac, F. J. (2010). Sobre Grafos Arco-Circulares Propios y Helly. PhD thesis, Universidad de Buenos Aires, Facultad de Ciencias Exactas y Naturales, Departamento de Computacion.

Szwarcfiter, J. L. (1997). Recognizing clique-Helly graphs. Ars Comb., 45:29–32.

Trotter, Jr., W. T. and Moore, Jr., J. I. (1976). Characterization problems for graphs, partially ordered sets, lattices, and families of sets. Discrete Mathematics, 16(4):361–381.