Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
From MaRDI portal
Publication:4068743
DOI10.2307/2319844zbMath0311.05109OpenAlexW4234132957WikidataQ55869690 ScholiaQ55869690MaRDI QIDQ4068743
Publication date: 1975
Published in: The American Mathematical Monthly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2319844
Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15) Coloring of graphs and hypergraphs (05C15)
Related Items
Certain topological indices and polynomials for the Isaac graphs ⋮ 5-Cycle Double Covers, 4-Flows, and Catlin Reduction ⋮ LACEABILITY PROPERTIES IN FLOWER SNARK GRAPHS ⋮ Finding a Perfect Phylogeny from Mixed Tumor Samples ⋮ On gap-labellings of some families of graphs ⋮ Handling symmetries in mixed-integer semidefinite programs ⋮ Edge colorings and circular flows on regular graphs ⋮ Roman domination and independent Roman domination on graphs with maximum degree three ⋮ On total coloring and equitable total coloring of infinite snark families ⋮ Reducible 3-critical graphs ⋮ Some snarks are worse than others ⋮ Rotationally symmetric snarks from voltage graphs ⋮ K2‐Hamiltonian graphs: II ⋮ Most Generalized Petersen graphs of girth 8 have cop number 4 ⋮ A survey of graphs with known or bounded crossing numbers ⋮ Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44 ⋮ Weakly convex and convex domination numbers for generalized Petersen and flower snark graphs ⋮ $K_2$-Hamiltonian Graphs: I ⋮ Graphs, friends and acquaintances ⋮ Superposition and constructions of graphs without nowhere-zero \(k\)-flows ⋮ On snarks that are far from being 3-edge colorable ⋮ Oddness to resistance ratios in cubic graphs ⋮ Cyclic connectivity, edge-elimination, and the twisted Isaacs graphs ⋮ Sigma coloring on powers of paths and some families of snarks ⋮ On a construction of Thomassen ⋮ The cost of perfection for matchings in graphs ⋮ On parsimonious edge-colouring of graphs with maximum degree three ⋮ Unnamed Item ⋮ A cyclically 6-edge-connected snark of order 118 ⋮ Counterexamples to a conjecture about bottlenecks in non-Tait-colourable cubic graphs ⋮ The construction and reduction of strong snarks ⋮ Tutte's edge-colouring conjecture ⋮ Cycle-saturated graphs of minimum size ⋮ The Fan–Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks ⋮ Circular flow numbers of regular multigraphs ⋮ The circular chromatic index of some Class 2 graphs ⋮ Computing the automorphic chromatic index of certain snarks ⋮ Even cycles and even 2-factors in the line graph of a simple graph ⋮ On type 2 snarks and dot products ⋮ Flows and generalized coloring theorems in graphs ⋮ Edge-colouring graphs with bounded local degree sums ⋮ Unnamed Item ⋮ Approximation of 3-Edge-Coloring of Cubic Graphs ⋮ Petersen Cores and the Oddness of Cubic Graphs ⋮ Construction of class two graphs with maximum vertex degree three ⋮ Even polyhedral decompositions of cubic graphs ⋮ Note sur la non existence d'un snark d'ordre 16 ⋮ On stable cycles and cycle double covers of graphs with large circumference ⋮ Even cycle decompositions of 4-regular graphs and line graphs ⋮ A note on using the resistance-distance matrix to solve Hamiltonian cycle problem ⋮ Pseudo and strongly pseudo 2-factor isomorphic regular graphs and digraphs ⋮ Real flow number and the cycle rank of a graph ⋮ Odd 2-factored snarks ⋮ Smallest maximally nonhamiltonian graphs ⋮ Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks. ⋮ Edge reductions in cyclically \(k\)-connected cubic graphs ⋮ Snarks of order 18 ⋮ Generation and properties of snarks ⋮ The hunting of a snark with total chromatic number 5 ⋮ Counting edge-Kempe-equivalence classes for 3-edge-colored cubic graphs ⋮ Fulkerson's conjecture and Loupekine snarks ⋮ Superposition of snarks revisited ⋮ The genus of Petersen powers ⋮ Snarks with special spanning trees ⋮ Stabilizer-based symmetry breaking constraints for mathematical programs ⋮ Reductions of Matrices Associated with Nowhere-Zero Flows ⋮ \(\lambda\)-numbers of several classes of snarks ⋮ The complexity of counting edge colorings for simple graphs ⋮ Measures of edge-uncolorability of cubic graphs ⋮ AVD-total-chromatic number of some families of graphs with \(\Delta(G) = 3\) ⋮ Saturation numbers for families of graph subdivisions ⋮ Smallest maximally nonhamiltonian graphs. II ⋮ On the smallest snarks with oddness 4 and connectivity 2 ⋮ Unnamed Item ⋮ On the partition and coloring of a graph by cliques ⋮ On Compatible Normal Odd Partitions in Cubic Graphs ⋮ Hamilton-chain saturated hypergraphs ⋮ 6-decomposition of snarks ⋮ The genesis of differential games in light of Isaacs' contributions ⋮ Some results on the structure of multipoles in the study of snarks ⋮ Smallest counterexample to the 5-flow conjecture has girth at least eleven ⋮ Complexity of approximation of 3-edge-coloring of graphs ⋮ Hamiltonian path saturated graphs with small size ⋮ Irreducible snarks of given order and cyclic connectivity ⋮ Altitude of regular graphs with girth at least five ⋮ Geometric coloring theory ⋮ Cycle double covers of infinite planar graphs ⋮ Families of dot-product snarks on orientable surfaces of low genus ⋮ Berge-Fulkerson coloring for some families of superposition snarks ⋮ The k-conversion number of regular graphs ⋮ An appreciation of Professor Rufus Isaacs ⋮ Colouring problems ⋮ Deterministic ``snakes and ladders heuristic for the Hamiltonian cycle problem ⋮ Large Isaacs' graphs are maximally non-Hamilton-connected ⋮ Balancing two spanning trees ⋮ A cycle-based formulation for the distance geometry problem ⋮ Triangle-free circuit decompositions and Petersen minor ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ On r-regular r-connected non-hamiltonian graphs ⋮ Measurements of edge-uncolorability ⋮ Color-character of uncolorable cubic graphs ⋮ Maximally non-hamiltonian graphs of girth 7 ⋮ Graphes cubiques d'indice trois, graphes cubiques isochromatiques, graphes cubiques d'indice quatre ⋮ A note on Berge-Fulkerson coloring ⋮ A note on semiextensions of stable circuits ⋮ Computational results and new bounds for the circular flow number of snarks ⋮ Classification and characterizations of snarks ⋮ Towards obtaining a 3-decomposition from a perfect matching ⋮ An algebraic theory of graph factorization ⋮ Nonorientable genera of Petersen powers ⋮ Computer based proofs by induction in graph theory - A house of cards? ⋮ Decompositions of Snarks into Repeated Dot-Products ⋮ Exponentially many hypohamiltonian snarks ⋮ The number of cycles in 2-factors of cubic graphs ⋮ On the metric dimensions for sets of vertices ⋮ The product of two high-frequency graph Laplacian eigenfunctions is smooth ⋮ Morphology of small snarks ⋮ Snarks from a Kászonyi perspective: a survey ⋮ Fano colourings of cubic graphs and the Fulkerson conjecture
This page was built for publication: Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
