ORDERED COLORINGS

被引：63

作者：

KATCHALSKI, M

MCCUAIG, W

SEAGER, S

机构：

[1] TECHNION ISRAEL INST TECHNOL,DEPT MATH,IL-32000 HAIFA,ISRAEL

[2] UNIV VICTORIA,DEPT MATH,VICTORIA,BC V8W 3P4,CANADA

[3] MT ST VINCENT UNIV,DEPT MATH,HALIFAX,NS B3M 2J6,CANADA

来源：

DISCRETE MATHEMATICS | 1995年 / 142卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(93)E0216-Q

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let k be a positive integer. An ordered k-colouring of a graph G is a function c from V(G) into {1,...,k} such that for every pair of distinct vertices x and y and for every (x,y)-path P, if c(x)=c(y), then there exists an internal vertex z of P such that c(x) < c(z). We prove some theorems on ordered colourings of trees and planar graphs, and examine the relationship between connectivity and ordered colourings. Let A be a set of graphs which is ordered by subgraphs and closed under subgraphs. We characterize when A is a well-quasi-order. A generalization of ordered colourings is given.

引用

页码：141 / 154

页数：14

共 14 条

[1]

BONDY JA, 1981, GRAPH THEORY APPLICA

[2] OPTIMIZING OVER THE SUBTOUR POLYTOPE OF THE TRAVELING SALESMAN PROBLEM [J].