Skip to main content
Article
Monochromatic Structures in Edge-Coloured Graphs and Hypergraphs - A Survey
International Journal of Graph Theory and its Applications
  • Shinya Fujita, Yokohama City University
  • Henry Liu, Universidade Nova de Lisboa
  • Colton Magnant, Georgia Southern University
Document Type
Article
Publication Date
6-1-2015
Disciplines
Abstract

Given a graph whose edges are coloured, on how many vertices can we find a monochromatic subgraph of a certain type, such as a connected subgraph, or a cycle, or some type of tree? Also, how many such monochromatic subgraphs do we need so that their vertex sets form either a partition or a covering of the vertices of the original graph? What happens for the analogous situations for hypergraphs? In this survey, we shall review known results and conjectures regarding these questions. In most cases, the edge-coloured (hyper)graph is either complete, or non-complete but with a density constraint such as having fixed independence number. For some problems, a restriction may be imposed on the edge-colouring, such as when it is a Gallai colouring (i.e. the edge-colouring does not contain a triangle with three distinct colours). Many examples of edgecolourings will also be presented, each one either showing the sharpness of a result, or supporting a possible conjecture.

Citation Information
Shinya Fujita, Henry Liu and Colton Magnant. "Monochromatic Structures in Edge-Coloured Graphs and Hypergraphs - A Survey" International Journal of Graph Theory and its Applications Vol. 1 Iss. 1 (2015) p. 3 - 56
Available at: http://works.bepress.com/colton_magnant/52/