2023/12/14 by Dibyayan Chakraborty, Chakraborty, Dibyayan, L. Sunil Chandran +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2312.08759
openalex publication_date 2023/12/14 · openalex created_date 2023/12/16 · openalex updated_date 2026/07/28
A class of graphs G is χ-bounded if there exists a function f such that χ(G) ≤ f(ω(G)) for each graph G ∈ G, where χ(G) and ω(G) are the chromatic and clique number of G, respectively. The square of a graph G, denoted as G2, is the graph with the same vertex set as G in which two vertices are adjacent when they are at a distance at most two in G. 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 B for which χ(B2) is Ω(((ω(B2))2 )/(log ω(B2))). 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 G, χ(G2) ≤ (3 ω(G2))/(2). 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 P is partite testable for the squares of bipartite graphs if for a bipartite graph G=(A,B,E), whenever the induced subgraphs G2[A] and G2[B] satisfies the property P then G2 also satisfies the property P. Here, we discuss whether some of the well-known graph properties like perfectness, chordality, (anti-hole)-freeness, etc. are partite testable or not. As a consequence, we prove that the squares of biconvex bipartite graphs are perfect.