分类: [弦图]

弦图染色问题

关于弦图和弦图的各类应用,陈丹琦的论文中已经介绍的非常清楚。 弦图与区间图 接下来我将用自己的语言解释一下弦图的染色问题 先来说几个概念 子图: 图$G=(V,E),G’=(V’,E’),V’\subseteq V,E’\subseteq E$,则认为G’是G的一个子图 诱导子图:图$G=(V,E),G’=(V’,E’),V’\subseteq V E={ (u,v)|u,v\in V,(u,v)\in E } $,则认为G’是G的一个诱导子图 团: 图G的一个子图$G’=(V’,E’)$,G’是关于V’的完全图 极 ......