English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A class of graphs $\mathcal{G}$ is $\chi$-bounded if there exists a function$f$ such that $\chi(G) \leq f(\omega(G))$ for each graph $G \in \mathcal{G}$,where $\chi(G)$ and $\omega(G)$ are the chromatic and clique number of $G$,respectively. The square of a graph $G$, denoted as $G^2$, is the graph withthe same vertex set as $G$ in which two vertices are adjacent when they are ata distance at most two in $G$. In this paper, we study the $\chi$-boundednessof squares of bipartite graphs and its subclasses. Note that the class ofsquares of graphs, in general, admit a quadratic $\chi$-binding function.Moreover there exist bipartite graphs $B$ for which $\chi\left(B^2\right)$ is$\Omega\left(\frac{\left(\omega\left(B^2\right)\right)^2 }{\log\omega\left(B^2\right)}\right)$. We first ask the following question: "Whatsub-classes of bipartite graphs have a linear $\chi$-binding function?" Wefocus on the class of convex bipartite graphs and prove the following result:for any convex bipartite graph $G$, $\chi\left(G^2\right) \leq \frac{3\omega\left(G^2\right)}{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 squaresof bipartite graphs. We say that a graph property $P$ is partite testable forthe squares of bipartite graphs if for a bipartite graph $G=(A,B,E)$, wheneverthe induced subgraphs $G^2[A]$ and $G^2[B]$ satisfies the property $P$ then$G^2$ also satisfies the property $P$. Here, we discuss whether some of thewell-known graph properties like perfectness, chordality, (anti-hole)-freeness,etc. are partite testable or not. As a consequence, we prove that the squaresof biconvex bipartite graphs are perfect.

$\chi$-binding functions for squares of bipartite graphs and its subclasses