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

    Identifiers