Classifying coloring graphs

被引：15

作者：

Beier, Julie ^{[1
]}

Fierson, Janet ^{[2
]}

Haas, Ruth ^{[3
]}

Russell, Heather M. ^{[4
]}

Shavo, Kara ^{[5
]}

机构：

[1] Earlham Coll, Dept Math, 801 Natl Rd West, Richmond, IN 47374 USA

[2] La Salle Univ, Dept Math & Comp Sci, 1900 West Olney Ave, Philadelphia, PA 19141 USA

[3] Smith Coll, Dept Math & Stat, Northampton, MA 01063 USA

[4] Univ Richmond, Dept Math & Comp Sci, 28 Westhampton Way, Richmond, VA 23173 USA

[5] Presbyterian Coll, Dept Math, 503 South Broad St, Clinton, SC 29325 USA

来源：

DISCRETE MATHEMATICS | 2016年 / 339卷 / 08期

基金：

美国国家科学基金会;

关键词：

Coloring graph; Reconfiguration graph; Proper colorings;

D O I：

10.1016/j.disc.2016.03.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Given a graph G, its k-coloring graph is the graph whose vertex set is the proper k-colorings of the vertices of G with two k-colorings adjacent if they differ at exactly one vertex. In this paper, we consider the question: Which graphs can be coloring graphs? In other words, given a graph H, do there exist G and k such that H is the k-coloring graph of G? We will answer this question for several classes of graphs and discuss important obstructions to being a coloring graph involving order, girth, and induced subgraphs. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：2100 / 2112

页数：13

共 20 条

[1]

[Anonymous], 2005, GRAPH THEORY

[2]

[Anonymous], 2013, ELECT NOTES DISCRETE, DOI [DOI 10.1016/J.ENDM.2013.10.040, 10.1016/j.endm.2013.10.040]

[3] Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings [J].

Brewster, Richard C. ;

Noel, Jonathan A. .

JOURNAL OF GRAPH THEORY, 2015, 80 (03) :173-198

[4] Connectedness of the graph of vertex-colourings [J].

Cereceda, Luis ;

van den Heuvel, Jan ;

Johnson, Matthew .

DISCRETE MATHEMATICS, 2008, 308 (5-6) :913-919

[5] Finding Paths Between 3-Colorings [J].

Cereceda, Luis ;

van den Heuvel, Jan ;

Johnson, Matthew .

JOURNAL OF GRAPH THEORY, 2011, 67 (01) :69-82

[6] Mixing 3-colourings in bipartite graphs [J].

Cereceda, Luis ;

van den Heuvel, Jan ;

Johnson, Matthew .

EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (07) :1593-1606

[7]

Choo Kelly, 2011, ARS MATH CONT, V4

[8]

Cohen M, 2014, ELECTRON J COMB, V21

[9] Randomly coloring sparse random graphs with fewer colors than the maximum degree [J].

Dyer, Martin ;

Flaxman, Abraham D. ;

Frieze, Alan M. ;

Vigoda, Eric .

RANDOM STRUCTURES & ALGORITHMS, 2006, 29 (04) :450-465

[10]

Feghali C, 2014, LECT NOTES COMPUT SC, V8635, P287, DOI 10.1007/978-3-662-44465-8_25

← 1 2 →