| Autor: |
Flesch, Breeann, Kawana, Jessica, Laison, Joshua D., Lapides, Dana, Partlow, Stephanie, Puleo, Gregory J. |
| Rok vydání: |
2017 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
We introduce a variation of interval graphs, called veto interval (VI) graphs. A VI graph is represented by a set of closed intervals, each containing a point called a veto mark. The edge $ab$ is in the graph if the intervals corresponding to the vertices $a$ and $b$ intersect, and neither contains the veto mark of the other. We find families of graphs which are VI graphs, and prove results towards characterizing the maximum chromatic number of a VI graph. We define and prove similar results about several related graph families, including unit VI graphs, midpoint unit VI (MUVI) graphs, and single and double approval graphs. We also highlight a relationship between approval graphs and a family of tolerance graphs. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
