𝔖 Bobbio Scriptorium
✦   LIBER   ✦

H-colouring bipartite graphs

✍ Scribed by John Engbers; David Galvin

Book ID
113698925
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
247 KB
Volume
102
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Total colouring regular bipartite graphs
Total colouring regular bipartite graphs is NP-hard
✍ Colin J.H. McDiarmid; AbdΓ³n SΓ‘nchez-Arroyo πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 437 KB

The total chromatic number of an arbitrary graph is the smallest number of colours needed to colour the edges and vertices of the graph so that no two adjacent or incident elements of the graph receive the same colour. In this paper we prove that the problem of determining the total chromatic number

Coloured matchings in bipartite graphs
Coloured matchings in bipartite graphs
✍ Kathie Cameron πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 213 KB

A theorem of states that for every n x n (n ~> 3) complete bipartite graph G such that every edge is coloured and each colour is the colour of at most two edges, there is a perfect matching whose edges have distinct colours. We give an O(n 2) algorithm for finding such a perfect matching. We show t

Elementary Bipartite Graphs and Unique C
Elementary Bipartite Graphs and Unique Colourability
✍ GΓ‘bor BacsΓ³ πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 44 KB

The Clique-Pair-Conjecture (CPC) states that a uniquely colourable perfect graph, different from a clique, contains two maximum size cliques having a two element symmetric difference. One can make an auxiliary graph B from a minimal counterexample for the CPC (if any exists), this B is bipartite. We

Colouring random graphs
Colouring random graphs
✍ Colin McDiarmid πŸ“‚ Article πŸ“… 1984 πŸ› Springer US 🌐 English βš– 674 KB