3- and 4-critical graphs of small even order

DOI10.1016/S0012-365X(96)00105-7zbMath0948.05032MaRDI QIDQ1357738

Eckhard Steffen, Gunnar Brinkmann

Publication date: 16 June 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

4-critical graphs3-critical graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Related Items

Finding Δ(Σ) for a surface σ of characteristic χ(Σ) = −5 ⋮ Hamiltonian cycles in critical graphs with large maximum degree ⋮ Lower bounds on the number of edges in edge-chromatic-critical graphs with fixed maximum degrees ⋮ Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic \(\epsilon \in \{-1, -2, -3\}\) ⋮ A Möbius-type gluing technique for obtaining edge-critical graphs ⋮ Chromatic-index-critical graphs of orders 13 and 14

Uses Software

• MOLGEN
• nauty

Cites Work

• Construction of class two graphs with maximum vertex degree three
• There are no edge-chromatic 4-critical graphs of order 12
• Numbers of cubic graphs
• Isomorph-Free Exhaustive Generation
• Fast generation of cubic graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: 3- and 4-critical graphs of small even order