Bichromatic Pb>4b>-composition schemes for perfect orderability

详细信息	查看全文 | 推荐本文 |

• 作者：Hayward ; R.B. ; Lenhart ; W.J.
• 关键词：Graph composition ; Pb>4b> ; Pb>4b>-structure ; Perfect order ; Perfectly orderable graph
• 刊名：Discrete Applied Mathematics
• 出版年：2004
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：May 30, 2004
• 卷：141
• 期：1-3
• 页码：161-183
• 文件大小：626 K

摘要

A Pb>4b> is an induced path with four vertices. A bichromatic Pb>4b> composition scheme is as follows: (1) start with two graphs with vertex sets of different colour, say black • and white mg align=center border=0 SRC=/images/glyphs/BK9.GIF>, (2) select a set of allowable four-vertex bichromatic sequences, for example {••••,mg align=center border=0 SRC=/images/glyphs/BK9.GIF>mg align=center border=0 SRC=/images/glyphs/BK9.GIF>mg align=center border=0 SRC=/images/glyphs/BK9.GIF>mg align=center border=0 SRC=/images/glyphs/BK9.GIF>,•mg align=center border=0 SRC=/images/glyphs/BK9.GIF>mg align=center border=0 SRC=/images/glyphs/BK9.GIF>•,mg align=center border=0 SRC=/images/glyphs/BK9.GIF>••mg align=center border=0 SRC=/images/glyphs/BK9.GIF>}, (3) add edges between the graphs so that in the composed graph each Pb>4b> is coloured with an allowable sequence. Answering a question of Chvátal, we determine all such schemes which preserve perfect orderability.