The Library
Between clique-width and linear clique-width of bipartite graphs
Tools
Tools
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
