Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Colouring planar mixed hypergraphs. | Colouring planar mixed hypergraphs André Kiindgen The Fields Institute 222 College St. Toronto Ont. M5T 3J1 Canada kundgen@member.ams.org Eric Mendelsohn Department of Mathematics University of Toronto 100 St. George St. Toronto Ont Canada mendelso@math.utoronto.ca Vitaly Voloshin Institute of Mathematics and Informatics Moldavian Academy of Sciences Academiei 5 Chisinau MD-2028 Moldova voloshin@math.mldnet.com Submitted June 5 2000 Accepted September 28 2000 Abstract A mixed hypergraph is a triple H V C D where V is the vertex set and C and D are families of subsets of V the C-edges and D-edges respectively. A fc-colouring of H is a mapping c V k such that each C-edge has at least two vertices with a Common colour and each D-edge has at least two vertices of Different colours. H is called a planar mixed hypergraph if its bipartite representation is a planar graph. Classic graphs are the special case of mixed hypergraphs when C and all the D-edges have size 2 whereas in a bi-hypergraph C D. We investigate the colouring properties of planar mixed hypergraphs. Specifically we show that maximal planar bi-hypergraphs are 2-colourable find formulas for their chromatic polynomial and chromatic spectrum in terms of 2-factors in the dual prove that their chromatic spectrum is gap-free and provide a sharp estimate on the maximum number of colours in a colouring. Supported by NSERC grant of Derek Corneil and the Fields Institute. tffhis research is supported by NSERC Canada OGP007621 and the Fields Institute. This research is supported by NSERC Canada OGP007621 OGP007268 and the Fields Institute. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R60 2 Keywords colourings of hypergraphs mixed hypergraphs planar graphs and hypergraphs colourability chromatic spectrum. 2000 Mathematics Subject Classification 05C15. 1 Introduction We use the standard graph and hypergraph terminology of Berge 1 2 and the mixed hypergraph terminology from 10 11 12 13 . Following Berge 1 2 a .
