Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\). (Russian. English summary) Zbl 1077.05039

Let \(G\) be a planar graph without 3-cycles. The authors investigate the following problem: When can a 3-coloring of the vertices of a face \(F\) of \(G\) be extended to a 3-coloring of the whole graph \(G\)? In previous papers they studied the cases in which \(F\) is a 5-face [V. A. Aksenov, Diskret. Analiz, Novosibirsk 26, 3-19 (1974; Zbl 0308.05107)] or a 6-face [V. A. Aksenov, O. V. Borodin, and A. N. Glebov, Diskretn. Anal. Issled. Oper., Ser. 1 10, 3–11 (2003; Zbl 1047.05014)]. In the present paper, necessary and sufficient conditions are obtained for the extensibility of a 3-coloring of the vertices of a 7-face \(F\) of a graph \(G\) without 3-cycles to the whole graph.


05C15 Coloring of graphs and hypergraphs
Full Text: EuDML EMIS