On 4-colorable robust critical graphs

Mark Anderson; Robert Brigham; Ronald D. Dutton; Richard Vitray; Jay Yellen

doi:10.47443/dml.2021.s107

Author(s)

Mark Anderson Department of Mathematics and Computer Science, Rollins College,Winter Park, FL 32789,USA

Robert Brigham Department of Mathematics, University of Central Florida,Orlando, FL 32816,USA

Ronald D. Dutton Department of Computer Science, University of Central Florida,Orlando, FL 32816,USA

Richard Vitray Department of Mathematics and Computer Science, Rollins College,Winter Park, FL 32789,USA

Jay Yellen Department of Mathematics and Computer Science, Rollins College,Winter Park, FL 32789,USA

Abstract

Given a proper k-coloring of a graph G, a vertex v is locally recolorable if there is a proper k-coloring of the graph that changes the color of v and limits any other color changes to the neighbors of v. The coloring is robust if every vertex is locally recolorable. The robust chromatic number of G, R(G), is the smallest number k for which G has a robust k-coloring. If R(G) = (G), the graph is -robust and if deleting any vertex of a -robust graph decreases R(G), the graph is -robustcritical. We conjecture that only complete graphs are -robust-critical. This paper investigates this conjecture for = 4 and supports the conjecture for a large class of such graphs. Furthermore, conditions that must be satisfied for such graphs are determined.

Publication Details

Page(s) 54-59

DOI 10.47443/dml.2021.s107

Published Journal: Discrete Mathematics Letters, Volume: 6, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords

robust coloring, chromatic number, -robust-critical

References

Anderson M.,Brigham R.,Dutton R.,Vitray R. .2014 .. , 94 : 287-302.

Chva V.,Bari F.,Harary F. .1974 .´tal, The minimality of the Mycielski graph. Graphs and Combinatorics (Lecture Notes in Mathematics 406), : 243-246.