Colored graphs without colorful cycles (Q949751): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Ales Pultr / rank | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Property / author | |||
Property / author: Ales Pultr / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Gabriel Semanisin / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2036460087 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1509.05621 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On lengths of rainbow cycles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lambda composition / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge-colored complete graphs with precisely colored subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transitiv orientierbare Graphen / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Edge colorings of complete graphs without tricolored triangles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4871773 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On classes of relations and graphs determined by subobjects and factorobjects / rank | |||
Normal rank |
Latest revision as of 18:46, 28 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Colored graphs without colorful cycles |
scientific article |
Statements
Colored graphs without colorful cycles (English)
0 references
21 October 2008
0 references
A cycle in a complete graph with coloured edges is called colourful if each of its edges has a different colour (such a subgraphs are sometimes called rainbow as well). It is shown that complete graphs with coloured edges do not have colourful cycles if and only if they are so-called Gallai graphs, i.e. graphs that do not possess colourful triangles. It is shown that the ommited edges of colourful cycles with the operation \(m\circ n = m+n-2\) form a monoid. The authors provide a characterisation of Gallai graphs and two characterization of the connected components of maximal monochromatic subgraphs of exact Gallai graphs. The characterizations of maximal monochromatic subgraphs are given in terms of full homomorphism and homomorphisms duality.
0 references
colourful cycle
0 references
rainbow colouring
0 references
monoid
0 references
Gallai graph
0 references
homomorphism
0 references