Between clique-width and linear clique-width of bipartite graphs



Alecu, Bogdan, Kante, Mamadou Moustapha, Lozin, Vadim and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2020) Between clique-width and linear clique-width of bipartite graphs. DISCRETE MATHEMATICS, 343 (8). p. 111926.

[img] Text
lcw-J_revision_final.pdf - Author Accepted Manuscript

Download (321kB) | Preview

Abstract

We consider hereditary classes of bipartite graphs where clique-width is bounded, but linear clique-width is not. Our goal is identifying classes that are critical with respect to linear clique-width. We discover four such classes and conjecture that this list is complete, i.e. a hereditary class of bipartite graphs of bounded clique-width that excludes a graph from each of the four critical classes has bounded linear clique-width.

Item Type: Article
Uncontrolled Keywords: 05C99, Linear clique-width, Bipartite cograph, Boundary class, Bounded clique width, L-critical graph
Depositing User: Symplectic Admin
Date Deposited: 04 May 2020 14:41
Last Modified: 18 Jan 2023 23:53
DOI: 10.1016/j.disc.2020.111926
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3085951