Color-reversal by local complementation (Q1820800): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(87)90240-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2035935207 / rank | |||
Normal rank |
Latest revision as of 12:06, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Color-reversal by local complementation |
scientific article |
Statements
Color-reversal by local complementation (English)
0 references
1987
0 references
A graph is said to be bicoloured if its vertices are coloured with two distinct colours. A local inversion at a vertex v of a connected bicoloured graph G is an operation on G which reverses the colours of the neighbours of v as well as the adjacency of the subgraph of G induced by the neighbours of v. As pointed out by the author, the notion of local inversion is a modification of another one which arises in an analysis of the fine structure of Eulerian walks studied in his paper ''Eulerian walks and local complementation'' - to appear in Eur. J. Comb. The following theorem is proved: Let G be a connected bicoloured graph of order \(n\geq 2\). Then G can be colour-reversed by taking at most \(6n+3\) local inversions. More generally, given two arbitrary bicolourations \(\beta\) and \(\beta\) ' of G, then \(\beta\) ' can be obtained from \(\beta\) by taking at most 9n local inversions.
0 references
local inversion
0 references
bicoloured graph
0 references