𝔖 Bobbio Scriptorium
✦   LIBER   ✦

NP-completeness of edge-colouring some restricted graphs

✍ Scribed by Leizhen Cai; John A. Ellis

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
850 KB
Volume
30
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Edge-coloured complete graphs: Connected
Edge-coloured complete graphs: Connectedness of some subgraphs
✍ Adam Idzik; Jan Komar; Marcin Malawski πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 435 KB

If the edges of a complete graph K,., m/> 4, are painted two colours so that monochromatic K " graphs are connected, then there exists an increasing sequence ( n)n~4 of complete subgraphs whose monochromatic subgraphs are also connected. For more than two colours this is not true, but an analogous f

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ JiΕ™Γ­ Fiala πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 63 KB πŸ‘ 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co

Properly coloured Hamiltonian paths in e
Properly coloured Hamiltonian paths in edge-coloured complete graphs
✍ J. Bang-Jensen; G. Gutin; A. Yeo πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 251 KB

We consider edge-coloured complete graphs. A path or cycle Q is called properly coloured (PC) if any two adjacent edges of Q differ in colour. Our note is inspired by the follou~ng conjecture by B. Bollobis and P. Erdijs (1976): if G is an edge-coloured complete graph on )I vertices in which the max