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

Aksenov, V. A.; Borodin, O. V.; Glebov, A. N.

Sib. Èlektron. Mat. Izv. 1, 117-128 (2004).

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.

Reviewer: A. Yu. Vesnin (Novosibirsk)

MSC:

05C15

Coloring of graphs and hypergraphs

Citations:

Zbl 0308.05107; Zbl 1047.05014