Scholarlink

<p>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 <i>ab</i> is in the graph if the intervals corresponding to the vertices <i>a</i> and <i>b</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Veto Interval Graphs and Variations

  • 期刊论文

  • 发表日期：

    2025年3月13日

查看全文
  • Breeann Flesch,
  • Jessica Kawana,
  • Joshua D. Laison,
  • Dana Lapides,
  • Stephanie Partlow,
  • Gregory J. Puleo

摘要

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.