2011/04/04 by José Antonio Martín H, H, José Antonio Martín
Computer Science · Mathematics · #05C69 #05C75 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Primary 05C15 #Secondary 05C90 #cs.CC #cs.DM #math.CO #msc:05C15 #msc:05C69 #msc:05C75 #msc:05C90
paper · pdf · doi:10.48550/arxiv.1104.0510
arxiv created 2011/04/04 · arxiv updated 2015/03/18
In this paper I study a variant of the general vertex coloring problem called precoloring. Specifically, I study graph precolorings, by developing new theory, for characterizing the minimal non-extensible precolorings. It is interesting per se that, for graphs of arbitrarily large chromatic number, the minimal number of colored vertices, in a non-extensible precoloring, remains constant; only two vertices u,v suffice. Here, the relation between such u,v is called an implicit-relation, distinguishing two cases: (i) implicit-edges where u,v are precolored with the same color and (ii) implicit-identities where u,v are precolored distinct.