No label defined (Q4487450)

It is shown that the overfull conjecture, which would provide a chromatic index characterization for a large class of graphs, and the conformability conjecture, which would provide a total chromatic number characterization for a large class of graphs, both in fact apply to almost all graphs, whether labelled or unlabelled. It is similarly shown that the biconformability conjecture, which would provide a total chromatic number characterization for a large class of equibipartite graphs, in fact applies to almost all equibipartite graphs. For this it is proved that (i) almost all labelled (or unlabelled) graphs \(G\) have \(\Delta (G)\geq \frac{1}{2}|V(G)|\); (ii) almost all labelled (or unlabelled) bicoloured equibipartite graphs \(G\) of order \(2n\) satisfy \(\Delta (G)\geq \frac{1}{4}|V(G)|\); (iii) almost all unlabelled bipartitioned equibipartite graphs \(G\) satisfy \(\Delta (G)\geq \frac{1}{4}|V(G)|\). Some of the arguments for unlabelled graphs are based on Pólya's theorem.