A new graph construction of unbounded clique-width.
Journal article
Korpelainen, Nicholas 2016. A new graph construction of unbounded clique-width. Electronic Notes in Discrete Mathematics. https://doi.org/10.1016/j.endm.2016.11.005
| Authors | Korpelainen, Nicholas |
|---|---|
| Abstract | We define permutation-partition graphs by replacing one part of a 2K2-free bipartite graph (a bipartite chain graph) by an induced linear forest. We show that this hereditary graph class is of of unbounded clique-width (with a new graph construction of large clique-width). We show that this graph class contains no minimal graph class of unbounded clique-width, and give a conjecture for a contained boundary class for this property. |
| Keywords | Clique-width; Hereditary class; Graph theory |
| Year | 2016 |
| Journal | Electronic Notes in Discrete Mathematics |
| Publisher | Elsevier |
| ISSN | 15710653 |
| Digital Object Identifier (DOI) | https://doi.org/10.1016/j.endm.2016.11.005 |
| Web address (URL) | http://hdl.handle.net/10545/622379 |
| http://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| hdl:10545/622379 | |
| Publication dates | 01 Dec 2016 |
| Publication process dates | |
| Deposited | 19 Mar 2018, 13:15 |
| Rights | Archived with thanks to Electronic Notes in Discrete Mathematics |
| Contributors | University of Derby |
| File | File Access Level Open |
| File | File Access Level Open |
Permalink -
https://repository.derby.ac.uk/item/93z36/a-new-graph-construction-of-unbounded-clique-width
Download files
60
total views0
total downloads6
views this month0
downloads this month
Export as
Related outputs
A boundary class for the k-path partition problem.
Korpelainen, Nicholas 2018. A boundary class for the k-path partition problem. Electronic Notes in Discrete Mathematics. https://doi.org/10.1016/j.endm.2018.05.009
Infinitely many minimal classes of graphs of unbounded clique-width.
Collins, Andrew, Foniok, Jan, Korpelainen, Nicholas, Lozin, Vadim and Zamaraev, Viktor 2017. Infinitely many minimal classes of graphs of unbounded clique-width. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2017.02.012Well-quasi-order for permutation graphs omitting a path and a clique
Korpelainen, Nicholas, Atminas, Aistis, Brignall, Robert, Vatter, Vincent and Lozin, Vadim 2015. Well-quasi-order for permutation graphs omitting a path and a clique. The Electronic Journal of Combinatorics.