The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Exponentially many perfect matchings in cubic graphs
Edge-colouring of joins of regular graphs. I
Decompositions for edge-coloring join graphs and cobipartite graphs
Matching structure and the matching lattice
Matchings in regular graphs
NP-completeness of edge-colouring some restricted graphs
How to find overfull subgraphs in graphs with large maximum degree
The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
Edge coloring regular graphs of high degree
Characterizing and edge-colouring split-indifference graphs
Graphok és alkalmazásuk a determinánsok és a halmazok elméletére. (Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.).
The theory of regular graphs
On the colouring of maps.
How to find overfull subgraphs in graphs with large maximum degree. II
Superposition and constructions of graphs without nowhere-zero \(k\)-flows
Classifying \(k\)-edge colouring for \(H\)-free graphs
On the chromatic index of join graphs and triangle-free graphs with large maximum degree
Counting \(r\)-graphs without forbidden configurations
Edge-colouring graphs with bounded local degree sums
Factorisation of snarks
Edge-colouring of regular graphs of large degree
Regular \(n\)-valent \(n\)-connected non-Hamiltonian non \(n\)-edge-colourable graphs
Exponentially many hypohamiltonian snarks
Set Partitioning via Inclusion-Exclusion
The chromatic index of graphs with a spanning star
The NP-Completeness of Edge-Coloring
Odd Minimum Cut-Sets and b-Matchings
The chromatic index of complete multipartite graphs
Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
Indecomposabler-graphs and some other counterexamples
Almost all regular graphs are hamiltonian
NP completeness of finding the chromatic index of regular graphs
Regular Graphs of High Degree are 1-Factorizable
The chromatic index of graphs of even order with many edges
Paths, Trees, and Flowers
Maximum matching and a polyhedron with 0,1-vertices
Polyhedral decompositions of cubic graphs
Network-Colourings
The overfull conjecture on split-comparability and split-interval graphs
Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
On an estimate of the chromatic class of a \(p\)-graph
On the chromatic index of complementary prisms

This page was built for publication: The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark