Graphs with prescribed maximal subgraphs and critical chromatic graphs
Graphs with prescribed size and vertex parities
Graphs with rainbow connection number two
An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this paper we prove that rc(G) = 2 for every connected graph G of order n and size m, where . We also characterize graphs with rainbow connection number two and large clique number.
Graphs with smallest sum of squares of vertex degrees