EUVIMEDEUVIMED entdecken
Crossref

χ‐Binding Functions for Squares of Convex Bipartite Graphs and Partite Testability for Bipartite Squares

Dibyayan Chakraborty, L. Sunil Chandran, Dalu Jacob, Raji R. Pillai

Journal of Graph Theory · 2026-07 · 112 (3) · 235-254

DOI: 10.1002/jgt.70014 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 23.03.2026. Verfasst von Dibyayan Chakraborty und 3 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A class of graphs is ‐bounded if there exists a function such that for each graph , where and are the chromatic and clique number of , respectively. The square of a graph , denoted as , is the graph with the same vertex set as in which two vertices are adjacent when they are at a distance at most two in . In this paper, we study the ‐boundedness of squares of bipartite graphs and its subclasses. Note that the class of squares of graphs, in general, admit a quadratic ‐binding function. Moreover, there exist bipartite graphs for which is . We first ask the following question: “What sub‐classes of bipartite graphs have a linear ‐binding function?” We focus on the class of convex bipartite graphs and prove the following result: for any convex bipartite graph , . Our proof also yields a polynomial‐time 3/2‐approximation algorithm for coloring squares of convex bipartite graphs. We then introduce a notion called “partite testable properties” for the squares of bipartite graphs. We say that a graph property is partite testable for the squares of bipartite graphs if for a bipartite graph , whenever the induced subgraphs and satisfies the property then also satisfies the property . Here, we discuss whether some of the well‐known graph properties like perfectness , chordality , (anti‐hole)‐freeness , and so on. are partite testable or not. As a consequence, we prove that the squares of biconvex bipartite graphs are perfect.

Zitieren

APA

Chakraborty, D., Chandran, L. S., Jacob, D., & Pillai, R. R. (2026). χ‐Binding Functions for Squares of Convex Bipartite Graphs and Partite Testability for Bipartite Squares. Journal of Graph Theory, 112(3), 235-254. https://doi.org/10.1002/jgt.70014

Vancouver

Chakraborty D, Chandran LS, Jacob D, Pillai RR. χ‐Binding Functions for Squares of Convex Bipartite Graphs and Partite Testability for Bipartite Squares. Journal of Graph Theory. 2026;112(3):235-254. doi:10.1002/jgt.70014

BibTeX
@article{Chakraborty2026,
  author = {Chakraborty, Dibyayan and Chandran, L. Sunil and Jacob, Dalu and Pillai, Raji R.},
  title = {χ‐Binding Functions for Squares of Convex Bipartite Graphs and Partite Testability for Bipartite Squares},
  journal = {Journal of Graph Theory},
  year = {2026},
  volume = {112},
  number = {3},
  pages = {235--254},
  doi = {10.1002/jgt.70014}
}
Kostenlos starten →