×

zbMATH — the first resource for mathematics

Restricted edge-colourings of bipartite graphs. (English) Zbl 0863.05039
Summary: Suppose each vertex of a bipartite multigraph (with partition \((X,Y))\) is assigned a set of colours; we say this colour scheme is feasible if the edges of the graph can be properly coloured so that each receives a colour in both of its endpoints’ sets. We prove various results showing that certain types of colour scheme are always feasible. For instance, we prove that if the colour scheme obtained by assigning the set \(\{1, \dots, d(x)\}\) of colours to each vertex \(x\) of \(X\) and the set \(T=\{1, \dots, t\}\) \((t\geq \Delta (X))\) to each vertex of \(Y\) is feasible, then so is every colour scheme where each vertex \(x\) of \(X\) gets \(d(x)\) colours from \(T\) and each vertex of \(Y\) gets the set \(T\).

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1112/plms/s3-47.3.507 · Zbl 0557.05013 · doi:10.1112/plms/s3-47.3.507
[2] Smetaniuk, Proof of the Evans conjecture. Ars Comb. 11 pp 155– (1981) · Zbl 0471.05013
[3] DOI: 10.1006/jctb.1995.1011 · Zbl 0826.05026 · doi:10.1006/jctb.1995.1011
[4] Fiorini, Research Notes in Mathematics 16 (1977)
[5] Hilton, Annals of Discrete Math. 13 pp 139– (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.