Clique Divergent Clockwork Graphs and Partial Orders
| Autor: | Miguel A. Pizaña, F. Larrión, Victor Neumann-Lara |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Block graph
Clique Discrete mathematics Clique-sum Applied Mathematics Comparability graph Clique (graph theory) Clique divergence Fixed-point property Clique graph Treewidth Combinatorics Least fixed point Clique problem Fixed point property Chordal graph Order dimension Discrete Mathematics and Combinatorics Split graph Iterated clique graphs Partially ordered set Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics. 7:10-13 |
| ISSN: | 1571-0653 |
| Popis: | S. Hazan and V. Neumann-Lara proved in 1996 that every finite partially ordered set whose comparability graph is clique null has the fixed point property and they asked whether there is a finite poset with the fixed point property whose comparability graph is clique divergent. In this work we answer that question by exhibiting such a finite poset. This is achieved by developing further the theory of clockwork graphs. We also show that there are polynomial time algorithms that recognize clockwork graphs and decide whether they are clique divergent. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect