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

ABSTRACT 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.