Orientable edge colorings of graphs

被引：0

作者：

Jamison, Robert E. ^{[1
,2
]}

机构：

[1] Clemson Univ, Clemson, SC 29634 USA

[2] Univ Haifa, IL-31999 Haifa, Israel

来源：

DISCRETE APPLIED MATHEMATICS | 2011年 / 159卷 / 07期

关键词：

Edge coloring; Directed graph; Orientation; Closure; Forbidden substructure; Recognition algorithm; RAMSEY NUMBERS;

D O I：

10.1016/j.dam.2010.05.010

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An edge coloring of a graph is orientable if and only if it is possible to orient the edges of the graph so that the color of each edge is determined by the head of its corresponding oriented arc. The goals of this paper include finding a forbidden substructure characterization of orientable colorings and giving a linear time recognition algorithm for orientable colorings. An edge coloring is lexical if and only if it is possible to number the vertices of the graph so that the color of each edge is determined by its lower endpoint. Lexical colorings are, of course, the orientable colorings in which the underlying orientation is acyclic. Lexical colorings play an important role in Canonical Ramsey theory, and it is this standpoint that motivates the current study. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：595 / 604

页数：10

共 8 条

[1] Aho A.V., 1995, Foundations of Computer Science
[2] Aho A. V., 1974, The design and analysis of computer algorithms
[3] CHEN G, 2001, 14 CUMB C
[4] Erdos P., 1950, J LOND MATH SOC, V25, P249
[5] Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs
[6] Constrained Ramsey numbers of graphs
Jamison, RE
Jiang, T
Ling, ACH
[J]. JOURNAL OF GRAPH THEORY, 2003, 42 (01) : 1 - 16
[7] On pattern Ramsey numbers of graphs
Jamison, RE
West, DB
[J]. GRAPHS AND COMBINATORICS, 2004, 20 (03) : 333 - 339
[8] New upper bounds for a canonical Ramsey problem
Jiang, T
Mubayi, D
[J]. COMBINATORICA, 2000, 20 (01) : 141 - 146

← 1 →