Relative colorings of graphs |
| |
Authors: | Paul C Kainen |
| |
Institution: | Department of Mathematics, Case Western Reserve University, Cleveland, Ohio 44106 USA |
| |
Abstract: | In this paper, the notion of relative chromatic number χ(G, H) for a pair of graphs G, H, with H a full subgraph of G, is formulated; namely, χ(G, H) is the minimum number of new colors needed to extend any coloring of H to a coloring of G. It is shown that the four color conjecture (4CC) is equivalent to the conjecture (R4CC) that χ(G, H) ≤ 4 for any (possibly empty) full subgraph H of a planar graph G and also to the conjecture (CR3CC) that χ(G, H) ≤ 3 if H is a connected and nonempty full subgraph of planar G. Finally, relative coloring theorems on surfaces other than the plane or sphere are proved. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|