Note on projective graphs

被引：14

作者：

Luczak, T ^{[1
]}

Nesetril, J

机构：

[1] Adam Mickiewicz Univ, Fac Math & Comp Sci, PL-61614 Poznan, Poland

[2] Charles Univ Prague, Fac Math & Phys, Int Theoret Comp Sci, ITI,Dept Appl Math, Prague, Czech Republic

来源：

JOURNAL OF GRAPH THEORY | 2004年 / 47卷 / 02期

关键词：

random graphs; graph homomorphisms; projective graphs;

D O I：

10.1002/jgt.20017

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that all graphs with a simple extension property are projective. As a consequence of this result we settle in the affirmative a conjecture of Larose and Tardif and characterize all homogeneous graphs which are projective. (C) 2004 Wiley Periodicals, Inc.

引用

页码：81 / 86

页数：6

共 19 条

[1]

ALON N, IN PRESS GEOM FUNCT

[2]

[Anonymous], 1975, RECENT ADV GRAPH THE

[3]

[Anonymous], 1993, ENCY MATH APPL, DOI DOI 10.1017/CBO9780511551574

[4]

BODIRSKY M, P COMPT SCI LOG 8 K

[5]

Bodnarcuk V. G., 1969, Kibernetika (Kiev), V5, P1

[6]

CHERLIN GL, 1992, COMPTEMP MATH, V131, P2

[7] APPLICATIONS OF PRODUCT COLORING [J].

GREENWELL, D ;

LOVASZ, L .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1974, 25 (3-4) :335-340

[8] ON THE COMPLEXITY OF H-COLORING [J].

HELL, P ;

NESETRIL, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (01) :92-110

[9]

Janson S, 2000, WIL INT S D

[10] On the algebraic structure of combinatorial problems [J].

Jeavons, P .

THEORETICAL COMPUTER SCIENCE, 1998, 200 (1-2) :185-204

← 1 2 →