Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\) (Q2577175)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\) |
scientific article |
Statements
Continuation of a 3-coloring from a 7-face onto a plane graph without \(C_3\) (English)
0 references
19 December 2005
0 references
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 [\textit{V.~A.~Aksenov}, Diskret. Analiz, Novosibirsk 26, 3-19 (1974; Zbl 0308.05107)] or a 6-face [\textit{V.~A.~Aksenov, O.~V.~Borodin}, and \textit{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.
0 references