The Chromatic Spectrum of Mixed Hypergraphs |
| |
| Authors: | Tao Jiang Dhruv Mubayi Zsolt Tuza Vitaly Voloshin Douglas B. West |
| |
| Affiliation: | (1) Department of Mathematics and Statistics, Miami University, Oxford, OH 45056, USA e-mail: jiangt@muohio.edu, US;(2) Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA e-mail: mubayi@microsoft.com, US;(3) Computer and Automation Institute, Hungarian Academy of Science, Republic of Hungary. e-mail: tuza@lutra.sztaki.hu, HU;(4) Institute of Mathematics and Informatics, Moldovan Academy of Sciences, Republic of Moldova. e-mail: voloshin@math.md, MD;(5) Department of Mathematics, University of Illinois, Urbane, IL 61801, USA e-mail: west@math.uiuc.edu, US |
| |
| Abstract: | A mixed hypergraph is a triple ℋ=(X, ?, ?), where X is the vertex set, and each of ?, ? is a list of subsets of X. A strict k-coloring of ℋ is a surjection c:X→{1,…,k} such that each member of ? has two vertices assigned a common value and each member of ? has two vertices assigned distinct values. The feasible set of H is {k: H has a strict k-coloring}. Among other results, we prove that a finite set of positive integers is the feasible set of some mixed hypergraph if and only if it omits the number 1 or is an interval starting with 1. For the set {s,t} with 2≤s≤t−2, the smallest realization has 2t−s vertices. When every member of ?∪? is a single interval in an underlying linear order on the vertices, the feasible set is also a single interval of integers. Received: May 24, 1999 Final version received: August 31, 2000 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
