Classifying the clique-width of \(H\)-free bipartite graphs

DOI10.1016/J.DAM.2015.06.030zbMATH Open1329.05228arXiv1402.7060OpenAlexW1581957840MaRDI QIDQ906431

Author name not available (Why is that?)

Publication date: 21 January 2016

Published in: (Search for Journal in Brave)

Abstract: Let $G$ be a bipartite graph, and let $H$ be a bipartite graph with a fixed bipartition $(B_H,W_H)$. We consider three different, natural ways of forbidding $H$ as an induced subgraph in $G$. First, $G$ is $H$-free if it does not contain $H$ as an induced subgraph. Second, $G$ is strongly $H$-free if $G$ is $H$-free or else has no bipartition $(B_G,W_G)$ with $B_{H}subseteq{B}_G$ and $W_{H}subseteq{W}_G$. Third, $G$ is weakly $H$-free if $G$ is $H$-free or else has at least one bipartition $(B_G,W_G)$ with $B_{H}otsubseteq{B}_G$ or $W_{H}otsubseteq{W}_G$. Lozin and Volz characterized all bipartite graphs $H$ for which the class of strongly $H$-free bipartite graphs has bounded clique-width. We extend their result by giving complete classifications for the other two variants of $H$-freeness.

Full work available at URL: https://arxiv.org/abs/1402.7060

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Classifying the clique-width of \(H\)-free bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q906431)