Biclique graph of bipartite permutation graphs. Groshaus, M., Guedes, A. L. P., & Puppo, J. P. Electronic Notes in Discrete Mathematics, 62:33–38, 2017. LAGOS'17 - IX Latin and American Algorithms, Graphs and Optimization.
Biclique graph of bipartite permutation graphs [link]Paper  doi  abstract   bibtex   
Abstract The biclique graph KB(G) is the intersection graph of bicliques of a graph G. The aim of our work is to recognize graphs that are biclique graphs of bipartite permutation graphs. In this paper we prove that the biclique graph of a bipartite permutation graph is a K1,4-free interval graph, and we present a characterization of such graphs and a characterization of a subclass that leads to a polynomial time recognition algorithm.
@article{GroshausGuedesPuppo2017,
title = "Biclique graph of bipartite permutation graphs",
journal = "Electronic Notes in Discrete Mathematics",
volume = "62",
pages = "33--38",
year = "2017",
note = "LAGOS'17 - {IX} Latin and American Algorithms, Graphs and Optimization.",
issn = "1571-0653",
doi = "10.1016/j.endm.2017.10.007",
url = "https://www.sciencedirect.com/science/article/pii/S1571065317302457",
abstract_url = {https://lipn.univ-paris13.fr/Lagos2017/abstracts_final_short.pdf},
author = "M. Groshaus and A. L. P. Guedes and J. P. Puppo",
keywords = "Bicliques",
keywords = "Biclique graphs",
keywords = "Bipartite permutation graphs ",
abstract = "Abstract The biclique graph KB(G) is the intersection graph of bicliques of a graph G. The aim of our work is to recognize graphs that are biclique graphs of bipartite permutation graphs. In this paper we prove that the biclique graph of a bipartite permutation graph is a K1,4-free interval graph, and we present a characterization of such graphs and a characterization of a subclass that leads to a polynomial time recognition algorithm. "
}

Downloads: 0