کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648147 1342394 2012 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Facial parity edge colouring of plane pseudographs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Facial parity edge colouring of plane pseudographs
چکیده انگلیسی

A facial parity edge colouring   of a connected bridgeless plane graph is such an edge colouring in which no two face-adjacent edges receive the same colour and, in addition, for each face ff and each colour cc, either no edge or an odd number of edges incident with ff is coloured with cc. Let χp′(G) denote the minimum number of colours used in such a colouring of GG. In this paper we prove that χp′(G)≤20 for any 2-edge-connected plane graph GG. In the case when GG is a 33-edge-connected plane graph the upper bound for this parameter is 1212. For GG being 44-edge-connected plane graph we have χp′(G)≤9. On the other hand we prove that some bridgeless plane graphs require at least 10 colours for such a colouring.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 17, 6 September 2012, Pages 2735–2740
نویسندگان
, , , ,