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