A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
From MaRDI portal
Publication:5811782
DOI10.1112/jlms/s1-27.1.85zbMath0046.41001OpenAlexW1975659026MaRDI QIDQ5811782
Publication date: 1952
Published in: Journal of the London Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/jlms/s1-27.1.85
Related Items
Strong complete minors in digraphs, A tight relation between series-parallel graphs and bipartite distance hereditary graphs, Lehman's Theorem and the Directed Steiner Tree Problem, Colouring series-parallel graphs, Constructing Graphs with No Immersion of Large Complete Graphs, $K_5^-$-Subdivision in 4-Connected Graphs, Topology of series-parallel networks, Almost all graphs with 1.44n edges are 3-colorable, Coloring graphs with forbidden minors, Clustered variants of Hajós' conjecture, Efficient Algorithms for Optimization and Selection on Series-Parallel Graphs, Geodesic geometry on graphs, Clique immersions and independence number, Hadwiger's Conjecture for Graphs with Forbidden Holes, Connectivity keeping trees in 3-connected or 3-edge-connected graphs, \(K_{6}\) minors in 6-connected graphs of bounded tree-width, Bounding the chromatic number of squares of \(K_4\)-minor-free graphs, Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs, Critical (\(P_5\), bull)-free graphs, Some results on \(k\)-critical \(P_5\)-free graphs, Some mader-perfect graph classes, Refined List Version of Hadwiger’s Conjecture, Sketchy tweets: ten minute conjectures in graph theory, Recent progress towards Hadwiger's conjecture, On the Gorensteinness of broken circuit complexes and Orlik-Terao ideals, Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor, Properties of 8-contraction-critical graphs with no \(K_7\) minor, Über endliche Graphen mit vorgegebenen Homomorphieeigenschaften. (On finite graphs with prescribed homotopy properties), Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, A Combinatorial Model for Series-Parallel Networks, Fractional coloring and the odd Hadwiger's conjecture, Unnamed Item, The extremal function for \(K_{9}\) minors, The determination of the total chromatic number of series-parallel graphs with \((G) \geq 4\), Reducing Hajós' 4-coloring conjecture to 4-connected graphs, Acyclically pushable bipartite permutation digraphs: an algorithm, The existence problem for colour critical linear hypergraphs, On critical 3-chromatic hypergraphs, Hadwiger number and chromatic number for near regular degree sequences, Normal forms for binary relations, Complexity of finding a join of maximum weight, A Weakening of the Odd Hadwiger's Conjecture, The Tutte Polynomial Characterizes Simple Outerplanar Graphs, On a coloring conjecture of Hajós, \(k\)-critical graphs in \(P_5\)-free graphs, Graph minor theory, Triangulations and the Hajós conjecture, \(k\)-critical graphs in \(P_5\)-free graphs, Graphs Containing TopologicalH, Hadwiger’s Conjecture, On separating sets of edges in contraction-critical graphs, The extremal function for \(K_{8}^{-}\) minors, The entire coloring of series-parallel graphs, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Unnamed Item, Disjoint Paths—A Survey, Circumference and Pathwidth of Highly Connected Graphs, A generalisation of matching and colouring, On the critical densities of minor-closed classes, Connected cutsets of a graph and triangle bases of the cycle space, Large immersions in graphs with independence number 3 and 4, On Halin subgraphs and supergraphs, On group choosability of total graphs, Point partition numbers: decomposable and indecomposable critical graphs, Minimum-maximal matching in series-parallel graphs, Subgraphs of colour-critical graphs, Note on a conjecture of Toft, Some generalizations of theorems on vertex coloring, Graph homomorphisms into the five-cycle, On a new reformulation of Hadwiger's conjecture, On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture, Fractional and integral colourings, Note on inseparability graphs of matroids having exactly one class of orientations, More on the rainbow disconnection in graphs, The search for chromatically unique graphs. II, Some remarks on even-hole-free graphs, Smallest \(C_{2 \ell + 1}\)-critical graphs of odd-girth \(2 k + 1\), Intersection graphs for families of balls in \(R^n\), On the connection between the chromatic number of a graph and the number of cycles covering a vertex or an edge, Hadwiger's conjecture (ḵ\(=6):\) Neighbour configurations of 6-vertices in contraction-critical graphs, Chromaticity of series-parallel graphs, On constructive methods in the theory of colour-critical graphs, On the core of a traveling salesman cost allocation game, Independent paths and \(K_{5}\)-subdivisions, Some recent progress and applications in graph minor theory, The minimum number of edges in 4-critical digraphs of given order, Distance constraints in graph color extensions, A relaxed Hadwiger's conjecture for list colorings, Bounds for minimum semidefinite rank from superpositions and cutsets, Special subdivisions of \(K_4\) and 4-chromatic graphs, RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties, On strongly \(\mathbb{Z}_{2s + 1}\)-connected graphs, Remarks on a conjecture of Barát and Tóth, Hadwiger's conjecture for graphs on the Klein bottle, The enumeration problem for color critical linear hypergraphs, Partitioning bispanning graphs into spanning trees, Detecting minors in matroids through triangles, Graph minors. XVI: Excluding a non-planar graph, On series-parallel extensions of uniform matroids, On Tutte's extension of the four-colour problem, Large minors in graphs with given independence number, On graphs with no induced subdivision of \(K_4\), Matroids and multicommodity flows, Generalized hypergraph coloring, On the extension of a partial metric to a tree metric, Ore's conjecture on color-critical graphs is almost true, Critical \((P_6, \mathrm{banner})\)-free graphs, List-colouring the square of a \(K_4\)-minor-free graph, Some remarks on the odd Hadwiger's conjecture, Complete graph immersions in dense graphs, On Hadwiger's number---A problem of the Nordhaus-Gaddum type, The edge density of critical digraphs, Partitioning sparse graphs into an independent set and a forest of bounded degree, A Brooks type theorem for the maximum local edge connectivity, Planar graphs with no 6-wheel minor, Note on robust critical graphs with large odd girth, Hajós' conjecture and cycle power graphs, A practical approach to the chromatic partition problem, On the structure of \(k\)-connected graphs without \(K_{k}\)-minor, Partial matroid representations, Some remarks on Hajós' conjecture, On group choosability of graphs. II, Contractibility and the Hadwiger conjecture, Clique immersions in graphs of independence number two with certain forbidden subgraphs, The regular matroids with no 5-wheel minor, Flow-contractible configurations and group connectivity of signed graphs, A Brooks-type result for sparse critical graphs, Hadwiger's conjecture for 3-arc graphs, Hajos' graph-coloring conjecture: Variations and counterexamples, Minor obstructions for apex-pseudoforests, The edge version of Hadwiger's conjecture, Connectivities for \(k\)-knitted graphs and for minimal counterexamples to Hadwiger's conjecture, Hadwiger's conjecture for proper circular arc graphs, Entire choosability of near-outerplane graphs, On the unimodality of the independent set numbers of a class of matroids, Linear connectivity forces large complete bipartite minors, List-coloring graphs without \(K_{4,k}\)-minors, Reguläre Graphen 3., 4. und 5. Grades mit vorgegebenen abstrakten Automorphismengruppen, Farbenzahlen und Zusammenhängen, Dichromatic number and forced subdivisions, Unendliche Graphen endlichen Grades mit vorgegebenen Eigenschaften, Graphentransformationen, Reguläre Graphen beliebigen Grades mit vorgegebenen Eigenschaften, Bemerkungen zu Hadwigers Vermutung, Minor-obstructions for apex sub-unicyclic graphs, The Kelmans-Seymour conjecture. IV: A proof, On the conjecture of Hajos, Cliques, minors and apex graphs, On list critical graphs, A Brooks-type bound for squares of \(K_{4}\)-minor-free graphs, Balanced cycles and holes in bipartite graphs, Immersion and clustered coloring, Hadwiger's conjecture for \(K_ 6\)-free graphs, Subdivisions of \(K_5\) in graphs containing \(K_{2,3}\), A cubic algorithm for the directed Eulerian subgraph problem, Sparse colour-critical hypergraphs, The maximum clique problem, Weighted modulo orientations of graphs and signed graphs
