Characterizing subclasses of cover-incomparability graphs by forbidden subposets

DOI10.1007/S11083-018-9470-7MaRDI QIDQ2314427zbMATH OpenOpenAlexWikidataFDO

Authors Jan Bok, Jana Maxová

Publication date 22 July 2019

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.03413

zbMATH Keywords

cover-incomparability graphgraphposet

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75) Combinatorics of partially ordered sets (06A07)

Abstract: In this paper we continue investigations of cover-incomparability graphs of finite partially ordered sets (see cite{Bres,Bres2,Bres3,Bres4} and cite{Max,MaxDH}). We consider in some detail the distinction between cover-preserving subsets and isometric subsets of a partially ordered set. This is critical to understanding why forbidden subposet characterizations of certain classes of cover-incomparability graphs in cite{Bres} and cite{Bres3} are not valid as presented. Here we provide examples, investigate the root of the difficulties, and formulate and prove valid revisions of these characterizations.

Recommendations

• Cographs which are cover-incomparability graphs of posets
• Ptolemaic and planar cover-incomparability graphs
• Cover-incomparability graphs of posets
• Which \(k\)-trees are cover-incomparability graphs?
• On the complexity of cover-incomparability graphs of posets

Cites work

• Cographs which are cover-incomparability graphs of posets
• Cover-incomparability graphs and 2-colored diagrams of posets
• Cover-incomparability graphs and chordal graphs
• Cover-incomparability graphs of posets
• On the complexity of cover-incomparability graphs of posets
• Which \(k\)-trees are cover-incomparability graphs?
• Which distance-hereditary graphs are cover-incomparability graphs?

Cited in

(9)

• A forbidden subgraph characterization of some graph classes using betweenness axioms
• Ptolemaic and chordal cover-incomparability graphs
• Cographs which are cover-incomparability graphs of posets
• Which \(k\)-trees are cover-incomparability graphs?
• Ptolemaic and planar cover-incomparability graphs
• Composition and product of cover-incomparability graphs
• Cover-incomparability graphs and 2-colored diagrams of posets
• Recognition of chordal graphs and cographs which are cover-incomparability graphs
• On the complexity of cover-incomparability graphs of posets

This page was built for publication: Characterizing subclasses of cover-incomparability graphs by forbidden subposets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2314427)