FLOWS AND GENERALIZED COLORING THEOREMS IN GRAPHS

被引：179

作者：

JAEGER, F

机构：

[1] Université Scientifique et Médicale de Grenoble, Laboratoire I.M.A.G., 38041 Grenoble Cédex

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1979年 / 26卷 / 02期

关键词：

D O I：

10.1016/0095-8956(79)90057-1

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An (oriented) graph H is said to be Fk(k ≥ 2) iff there exists an integer flow in H with all edge-values in [1 - k, -1] {smile} [1, k - 1]. It is known that a plane 2-edge-connected graph is face-colorable with k colors (k ≥ 2) iff it is Fk; W. T. Tutte has proposed [1] to seek for extensions to general graphs of coloring results known for planar graphs through the use of the Fk property. In this direction, we prove among other results that every 2-edge-connected graph is F8. © 1979.

引用

页码：205 / 216

页数：12

共 21 条

[1] Berge C, 1970, GRAPHES HYPERGRAPHES
[2] DECOMPOSITION FOR COMBINATORIAL GEOMETRIES
BRYLAWSKI, TH
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 171 (SEP) : 235 - 282
[3] Crapo H. H., 1969, AEQUATIONES MATH, V3, P211, DOI DOI 10.1007/BF01817442
[4] MINIMUM PARTITION OF A MATROID INTO INDEPENDENT SUBSETS
EDMONDS, J
[J]. JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2): : 67 - +
[5] GROTZSCH H, 1958, WISS Z M LUTHER U MN, V8, P109
[6] Grunbaum B., 1963, MICHIGAN MATH J, V10, P303
[7] Harary F., 1969, GRAPH THEORY, DOI DOI 10.21236/AD0705364
[8] INFINITE FAMILIES OF NONTRIVIAL TRIVALENT GRAPHS WHICH ARE NOT TAIT COLORABLE
ISAACS, R
[J]. AMERICAN MATHEMATICAL MONTHLY, 1975, 82 (03) : 221 - 239
[9] BALANCED VALUATIONS AND FLOWS IN MULTIGRAPHS
JAEGER, F
[J]. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 55 (01) : 237 - 242
[10] KAINEN PC, 1970, COMBINATORIAL STRUCT

← 1 2 3 →