Dimension, graph and hypergraph coloring
type: Item
instance of: scholarly article
title: Dimension, graph and hypergraph coloring
zbMATH Open document ID: 0968.06002
DOI: 10.1023/A:1006429830221
author: Stefan Felsner
author: William T. Trotter
published in: Order
publication date: 2001-09-12T00:00:00Z
review text: A linear extension \(L\) of a poset \(P\) reverses an incomparable pair \((x,y)\) of \(P\) if \(x>y\) in \(L\). A set \(S\) of incomparable pairs forms a strict alternating cycle of \(P\) if no linear extension of \(P\) reverses all pairs in \(S\) but for all \(T \subset S\) there is a linear extension of \(P\) which reverses all pairs in \(T\). For a poset \(P = (X,\leq)\) let \(H_P = (V,E)\) be the hypergraph of incomparable pairs defined by \(V = \{(x,y) : x,y \in X\) and \(x \|y\}\) and \(E = \{S : S \subseteq V\) is a strict alternating cycle of \(P\}\). The graph of incomparable pairs is \(G_P = (V,E')\) with \(E' = \{S : S \in E\) and \(|S|=2\}\). Then dim\((P) = \chi(H_P) \geq \chi(G_P)\). The paper provides a new proof of the following theorem by Cogis: dim\((P)=2\) if and only if \(\chi(G_P)=2\) for every poset \(P\) that is not a total order. For all \(t \geq 2\) a poset \(P_t\) of dimension dim\((P_t) \geq (3/2)^{t-1}\) is constructed such that the chromatic number fulfills \(\chi(G_{P_t}) \leq 3t-4\).
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 1545465
zbMATH Keywords: dimension
zbMATH Keywords: chromatic number
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1545465