χ‐Binding Functions for Squares of Convex Bipartite Graphs and Partite Testability for Bipartite Squares
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.
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}
}
EUVIMED