
The Library
Between clique-width and linear clique-width of bipartite graphs
Tools
Alecu, Bogdan, Kanté, Mamadou Moustapha, Lozin, Vadim V. and Zamaraev, Viktor (2020) Between clique-width and linear clique-width of bipartite graphs. Discrete Mathematics, 343 (8). 111926. doi:10.1016/j.disc.2020.111926 ISSN 0012-365X.
|
PDF
WRAP-Between-clique-width-linear-clique-width-bipartite-graph-Lozin-2020.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (489Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.disc.2020.111926
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: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Bipartite graphs, Combinatorial analysis , Graph theory -- Data processing | ||||||||
Journal or Publication Title: | Discrete Mathematics | ||||||||
Publisher: | Elsevier BV | ||||||||
ISSN: | 0012-365X | ||||||||
Official Date: | August 2020 | ||||||||
Dates: |
|
||||||||
Volume: | 343 | ||||||||
Number: | 8 | ||||||||
Article Number: | 111926 | ||||||||
DOI: | 10.1016/j.disc.2020.111926 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 22 April 2020 | ||||||||
Date of first compliant Open Access: | 16 April 2021 | ||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year