arXiv:0709.1935 Abstract | arXiv Analytics

arXiv:0709.1935 [math.CO]Abstract References Reviews Resources

Clique-width of unit interval graphs

Published 2007-09-12Version 1

The clique-width is known to be unbounded in the class of unit interval graphs. In this paper, we show that this is a minimal hereditary class of unbounded clique-width, i.e., in every hereditary subclass of unit interval graphs the clique-width is bounded by a constant.

Comments: 9 pages, 1 figure

Categories: math.CO

Subjects: 05C75

Keywords: unit interval graphs, minimal hereditary class, hereditary subclass, unbounded clique-width

Related articles: Most relevant | Search more

arXiv:1503.01628 [math.CO] (Published 2015-03-05)

Minimal Classes of Graphs of Unbounded Clique-width and Well-quasi-ordering

A. Atminas, R. Brignall, V. Lozin, J. Stacho

arXiv:2203.15446 [math.CO] (Published 2022-03-29)

A framework for minimal hereditary classes of graphs of unbounded clique-width

Robert Brignall, Daniel Cocks

arXiv:1701.08857 [math.CO] (Published 2017-01-30)