scientific article; zbMATH DE number 1463391
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.
- A new proof of Grünbaum's 3 color theorem
- Vertex-splitting and chromatic index critical graphs
- A note on the three color problem
- The Erdős-Hajnal conjecture for three colors and triangles
- Constructive generation of very hard 3-colorability instances
- Bordeaux 3-color conjecture and 3-choosability
- scientific article; zbMATH DE number 5139507 (Why is no real title available?)
- scientific article; zbMATH DE number 2061160 (Why is no real title available?)
- scientific article; zbMATH DE number 3999957 (Why is no real title available?)
- The overfull conjecture and the conformability conjecture
- Graphs with full rank 3-color matrix and few 3-colorings
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4487450)
