Edge-coloured complete graphs: Connectedness of some subgraphs

DOI10.1016/0012-365X(87)90124-5MaRDI QIDQ1120587zbMATH OpenOpenAlexFDO

Authors Adam Idzik, Jan Komar, Marcin Malawski

Publication date 1987

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(87)90124-5

zbMATH Keywords

edge colouringmonochromatic separating edge set

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Review text

The main result of the paper is as follows: If the edges of the complete graph \(K_ n\) on n vertices are coloured in such a way that there is no monochromatic separating edge set, then there is a monotone sequence \(K_ m\) of complete subgraphs on m vertices for \(m=4,...,n\) so that also \(K_ m\) does not contain a monochromatic separating edge set.

Recommendations

• Heredity properties of connectedness in edge-coloured complete graphs
• scientific article; zbMATH DE number 4049669
• Highly connected monochromatic subgraphs of two-colored complete graphs
• Connected colorings of graphs.
• Estimation of cut-vertices in edge-coloured complete graphs

Cites work

• Complete graphs without polychromatic circuits
• scientific article; zbMATH DE number 3654142 (Why is no real title available?)
• scientific article; zbMATH DE number 3545568 (Why is no real title available?)
• Parallel concepts in graph theory

Cited in

(4)

• Connected tropical subgraphs in vertex-colored graphs
• Estimation of cut-vertices in edge-coloured complete graphs
• Connected colorings of graphs.
• Properly edge-coloured subgraphs in colourings of bounded degree

This page was built for publication: Edge-coloured complete graphs: Connectedness of some subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1120587)