Answers are grounded in this paper and cite their sources.
This research explores graph binding functions and properties in convex bipartite graphs, indicating new testability results.
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.
No takes yet. Share an insight, caveat, or question.
Chakraborty et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: