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

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

Cites Work

Paths, Trees, and Flowers
The NP-Completeness of Edge-Coloring
Maximum matching and a polyhedron with 0,1-vertices
The chromatic index of complete multipartite graphs
Title not available (Why is that?)
Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
Polyhedral decompositions of cubic graphs
Set partitioning via inclusion-exclusion
Title not available (Why is that?)
Title not available (Why is that?)
On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
NP completeness of finding the chromatic index of regular graphs
Exponentially many perfect matchings in cubic graphs
Title not available (Why is that?)
Matching structure and the matching lattice
Odd Minimum Cut-Sets and b-Matchings
How to find overfull subgraphs in graphs with large maximum degree
The chromatic index of graphs with a spanning star
Almost all regular graphs are hamiltonian
Title not available (Why is that?)
Decompositions for edge-coloring join graphs and cobipartite graphs
Regular Graphs of High Degree are 1-Factorizable
NP-completeness of edge-colouring some restricted graphs
Characterizing and edge-colouring split-indifference graphs
Matchings in regular graphs
Indecomposabler-graphs and some other counterexamples
Title not available (Why is that?)
Title not available (Why is that?)
Superposition and constructions of graphs without nowhere-zero \(k\)-flows
Edge-colouring graphs with bounded local degree sums
Factorisation of snarks
Network-Colourings
Regular \(n\)-valent \(n\)-connected non-Hamiltonian non \(n\)-edge-colourable graphs
Title not available (Why is that?)
Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
The chromatic index of graphs of even order with many edges
Classifying \(k\)-edge colouring for \(H\)-free graphs
On the chromatic index of join graphs and triangle-free graphs with large maximum degree
Title not available (Why is that?)
Edge coloring regular graphs of high degree
How to find overfull subgraphs in graphs with large maximum degree. II
Edge-colouring of regular graphs of large degree
Edge-colouring of joins of regular graphs. I
The NP-completeness of chromatic index in triangle free graphs with maximum vertex of degree 3
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.
Counting \(r\)-graphs without forbidden configurations
Exponentially many hypohamiltonian snarks
The overfull conjecture on split-comparability and split-interval 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6550846)