Diconnected Orientations and a Conjecture of Las Vergnas
Diconnected Orientations and a Conjecture of Las Vergnas
复制标题
DOI：
10.1112/jlms/s2-14.2.277
复制
发表时间：
1976-11
影响因子：
1.2
通讯作者：
J. Bondy
中科院分区：
文献类型：
--
作者：
J. Bondy
我们使用[1]中的术语和符号。特别地，如果D是有向图，则V表示它的点集，x表示色数；如果对于任意两个顶点u和v，D中存在从u到v的有向路，则D是双连通的。las Vergnas[6]猜想，如果D是双连通的且至少有两个顶点，则D至少包含一个长度为x的有向圈。在本文中，我们证明了las Vergnas的猜想。为了下面的定义和随后引理的目的，我们假设D是一个有向图，它的最长有向圈的长度为n^2，S是V的非空子集，c：S-*·{i，2，…，N}是S的一个着色.S迹是D中的一条有向迹，它的起点和终点都在S，其内部顶点是不同的，构成F\S的一个非空子集.如果P是长度为f的起点为u，终点为v的S迹，我们设
We use the terminology and notation of [1]. In particular, if D is a digraph, then V denotes its vertex set and x its chromatic number; and D is diconnected if, for any two vertices u and v, there is a directed path in D from u to v. Las Vergnas [6] conjectured that if D is diconnected and has at least two vertices, then D contains a directed cycle of length at least x-In this note, we prove Las Vergnas' conjecture.For the purpose of the following definitions and subsequent lemma, we shall assume that D is a digraph whose longest directed cycle has length n^ 2, that S is a non-empty subset of V, and that c: S-*•{I, 2,..., n} is a colouring of S. An S-trail is a directed trail in D whose origin and terminus lie in S, and whose internal vertices are distinct and form a non-empty subset of F\S. If P is an S-trail of length/, with origin u and terminus v, we set