Note about the upper chromatic number of mixed hypertrees
A mixed hypergraph is a triple H=(X,C,D), where X is the vertex set and each of C,D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of H is a mapping c:→[k] such that each C-edge has two vertices with a common color and each D-edge has two vertices with distin...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
Vladimir Andrunachievici Institute of Mathematics and Computer Science
2005-10-01
|
Series: | Computer Science Journal of Moldova |
Online Access: | http://www.math.md/files/csjm/v13-n2/v13-n2-(pp131-135).pdf |
_version_ | 1798041633183236096 |
---|---|
author | Kenneth Roblee Vitaly Voloshin |
author_facet | Kenneth Roblee Vitaly Voloshin |
author_sort | Kenneth Roblee |
collection | DOAJ |
description | A mixed hypergraph is a triple H=(X,C,D), where X is the vertex set and each of C,D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of H is a mapping c:→[k] such that each C-edge has two vertices with a common color and each D-edge has two vertices with distinct colors. Upper chromatic number is the maximum number of colors that can be used in a proper coloring. A mixed hypergraph H is called a mixed hypertree if there exists a host tree on the vertex set X such that every edge (C- or D-) induces a connected subtree of this tree.
We show that if a mixed hypertree can be decomposed into interval mixed hypergraphs then the upper chromatic number can be computed using the same formula. |
first_indexed | 2024-04-11T22:24:11Z |
format | Article |
id | doaj.art-f6fdd54152c3447c9f5da896e0fd2bff |
institution | Directory Open Access Journal |
issn | 1561-4042 |
language | English |
last_indexed | 2024-04-11T22:24:11Z |
publishDate | 2005-10-01 |
publisher | Vladimir Andrunachievici Institute of Mathematics and Computer Science |
record_format | Article |
series | Computer Science Journal of Moldova |
spelling | doaj.art-f6fdd54152c3447c9f5da896e0fd2bff2022-12-22T03:59:55ZengVladimir Andrunachievici Institute of Mathematics and Computer ScienceComputer Science Journal of Moldova1561-40422005-10-01132(38)131135Note about the upper chromatic number of mixed hypertreesKenneth Roblee0Vitaly Voloshin1Department of Mathematics and Physics, Troy University, Troy, Alabama, USADepartment of Mathematics and Physics, Troy University, Troy, Alabama, USAA mixed hypergraph is a triple H=(X,C,D), where X is the vertex set and each of C,D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of H is a mapping c:→[k] such that each C-edge has two vertices with a common color and each D-edge has two vertices with distinct colors. Upper chromatic number is the maximum number of colors that can be used in a proper coloring. A mixed hypergraph H is called a mixed hypertree if there exists a host tree on the vertex set X such that every edge (C- or D-) induces a connected subtree of this tree. We show that if a mixed hypertree can be decomposed into interval mixed hypergraphs then the upper chromatic number can be computed using the same formula.http://www.math.md/files/csjm/v13-n2/v13-n2-(pp131-135).pdf |
spellingShingle | Kenneth Roblee Vitaly Voloshin Note about the upper chromatic number of mixed hypertrees Computer Science Journal of Moldova |
title | Note about the upper chromatic number of mixed hypertrees |
title_full | Note about the upper chromatic number of mixed hypertrees |
title_fullStr | Note about the upper chromatic number of mixed hypertrees |
title_full_unstemmed | Note about the upper chromatic number of mixed hypertrees |
title_short | Note about the upper chromatic number of mixed hypertrees |
title_sort | note about the upper chromatic number of mixed hypertrees |
url | http://www.math.md/files/csjm/v13-n2/v13-n2-(pp131-135).pdf |
work_keys_str_mv | AT kennethroblee noteabouttheupperchromaticnumberofmixedhypertrees AT vitalyvoloshin noteabouttheupperchromaticnumberofmixedhypertrees |