Polychromatic colorings of complete graphs with respect to 1-, 2-factors and Hamiltonian cycles

被引：4

作者：

Axenovich, Maria ^{[1
]}

Goldwasser, John ^{[2
]}

Hansen, Ryan ^{[2
]}

Lidicky, Bernard ^{[3
]}

Martin, Ryan R. ^{[3
]}

Offner, David ^{[4
]}

Talbot, John ^{[5
]}

Young, Michael ^{[3
]}

机构：

[1] Karlsruhe Inst Technol, Dept Math, Karlsruhe, Germany

[2] West Virginia Univ, Dept Math, Morgantown, WV 26506 USA

[3] Iowa State Univ, Dept Math, Ames, IA 50011 USA

[4] Westminster Coll, Dept Math & Comp Sci, New Wilmington, PA 16172 USA

[5] UCL, Dept Math, London, England

来源：

JOURNAL OF GRAPH THEORY | 2018年 / 87卷 / 04期

基金：

美国国家科学基金会;

关键词：

1-factor; 2-factor; hamiltonian cycle; polychromatic coloring; DECOMPOSITION; HYPERCUBE;

D O I：

10.1002/jgt.22180

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G. The H-polychromatic number of G, denoted poly H(G), is the largest number of colors such that G has an H-polychromatic coloring. In this article, poly H(G) is determined exactly when G is a complete graph and H is the family of all 1-factors. In addition polyH(G) is found up to an additive constant term when G is a complete graph and H is the family of all 2-factors, or the family of all Hamiltonian cycles.

引用

页码：660 / 671

页数：12

共 12 条

[1]

Ackerman E, 2016, LEIBNIZ INT P INFORM

[2] Turan's theorem in the hypercube [J].

Alon, Noga ;

Krech, Anja ;

Szabo, Tibor .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (01) :66-72

[3] Polychromatic Colorings of Plane Graphs [J].

Alon, Noga ;

Berke, Robert ;

Buchin, Kevin ;

Buchin, Maike ;

Csorba, Peter ;

Shannigrahi, Saswata ;

Speckmann, Bettina ;

Zumstein, Philipp .

DISCRETE & COMPUTATIONAL GEOMETRY, 2009, 42 (03) :421-442

[4]

Bialostocki A., 1983, ARS COMBINATORIA, V16, P39

[5] COVER-DECOMPOSITION AND POLYCHROMATIC NUMBERS [J].

Bollobas, Bela ;

Pritchard, David ;

Rothvoss, Thomas ;

Scott, Alex .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) :240-256

[6] Split and balanced colorings of complete graphs [J].

Erdos, P ;

Gyárfás, A .

DISCRETE MATHEMATICS, 1999, 200 (1-3) :79-86

[7]

Goddard W., ARXIV160909684

[8]

Goldwasser J., 2017, POLYCHROMATIC UNPUB

[9]

Goldwasser J., 2016, ARXIV160305865

[10]

Gyarfas A., ARXIV13071768V1

← 1 2 →