Graph Theory and Probability
From MaRDI portal
Publication:3253064
DOI10.4153/CJM-1959-003-9zbMath0084.39602OpenAlexW4229970255WikidataQ55869075 ScholiaQ55869075MaRDI QIDQ3253064
Publication date: 1959
Published in: Canadian Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4153/cjm-1959-003-9
Related Items
THE LATTICE OF SUPER-BELNAP LOGICS, On decomposition of graphs, The Micro-world of Cographs, CONNECTEDNESS INDEX OF UNCERTAIN GRAPH, Unnamed Item, Probabilistic combinatorics and the recent work of Peter Keevash, Subgraphs of Kneser graphs with large girth and large chromatic number, On Random Representable Matroids, Ramsey properties of orientations of graphs, Linear-Time Approximation Algorithms for the Max Cut Problem, Asymptotic bounds on total domination in regular graphs, On generalized graph colorings, The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices, Clustered variants of Hajós' conjecture, Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs, The circular chromatic number of series-parallel graphs with large girth, Pure pairs. IV: Trees in bipartite graphs, Omitting Types in Fragments and Extensions of First Order Logic, Polynomial bounds for chromatic number. I. Excluding a biclique and an induced tree, THE CHROMATIC NUMBER OF -FREE GRAPHS, Polynomial bounds for chromatic number. III. Excluding a double star, Coloring of some crown-free graphs, Unnamed Item, Harnessing the Bethe free energy, Girth and λ $\lambda $‐choosability of graphs, On Two Problems in Ramsey--Turán Theory, An optimal χ‐bound for (P6, diamond)‐free graphs, Pure pairs. X. Tournaments and the strong Erdős-Hajnal property, On the chromatic number of \(P_5\)-free graphs with no large intersecting cliques, Making an H $H$‐free graph k $k$‐colorable, Bounds for the chromatic number of some \(pK_2\)-free graphs, On the chromatic number of (P5,dart)-free graphs, Coloring of a superclass of \(2K_2\)-free graphs, On sparse parity check matrices (extended abstract), Burling graphs revisited. III: Applications to \(\chi \)-boundedness, Ramsey properties of semilinear graphs, Unnamed Item, Extremal problems in hypergraph colourings, Polynomial \(\chi\)-binding functions for \(t\)-broom-free graphs, Make a graph singly connected by edge orientations, Existence of paths with \(t\) blocks in \(k ( t )\)-chromatic digraph, A Ramsey–Turán theory for tilings in graphs, Hitting all maximum stable sets in \(P_5\)-free graphs, A Generalization of $$\chi $$-Binding Functions, Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree, A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs, Triangle-free subgraphs with large fractional chromatic number, Unnamed Item, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Coloring graphs with fixed genus and girth, Online Graph Exploration: New Results on Old and New Algorithms, Almost all graphs with high girth and suitable density have high chromatic number, Box and Segment Intersection Graphs with Large Girth and Chromatic Number, A Class of Three‐Colorable Triangle‐Free Graphs, The Distance-t Chromatic Index of Graphs, On circuits and subgraphs of chromatic graphs, Forbidden ordered subgraph vs. forbidden subgraph characterizations of graph classes, Acyclic colorings of planar graphs, Strongly representable atom structures of relation algebras, Erdős Graphs Resolve Fine's Canonicity Problem, A structure theorem for graphs with no cycle with a unique chord and its consequences, Fast distributed algorithms for testing graph properties, On the complexity of distributed graph coloring with local minimality constraints, A Separator Theorem for String Graphs and its Applications, A Separator Theorem for String Graphs and Its Applications, Local chromatic number and distinguishing the strength of topological obstructions, Algorithmic bounds for the chromatic number†, On cycle—Complete graph ramsey numbers, On the chromatic number of (P_{5},windmill)-free graphs, Coloring-flow duality of embedded graphs, Canonical varieties with no canonical axiomatisation, Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs, INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS, Claw‐decompositions and tutte‐orientations, Coloring and Maximum Independent Set of Rectangles, Approximability Distance in the Space of H-Colourability Problems, The plane-width of graphs, Introducing Quasirandomness to Computer Science, Strongly representable atom structures of cylindric algebras, Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces, The circular chromatic number of a digraph, Atom-canonicity in varieties of cylindric algebras with applications to omitting types in multi-modal logic, A Simple Construction to Prove Mycielski’s Theorem, Tournaments and Semicomplete Digraphs, Splittings in varieties of logic, Small clique and large chromatic number, On the Plane-Width of Graphs, Interpolation in Logiken monotoner systeme, A review of random graphs, Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Point Partition Numbers and Girth, RECURSIVE AXIOMATISATIONS FROM SEPARATION PROPERTIES, On the dimension of a graph, On chromatic number of graphs and set-systems, The Erdös-Hajnal Conjecture-A Survey, Zur Geometrie der Kreislagerungen, On chromatic number of finite set-systems, Partition relations for cardinal numbers, Independent sets in k-chromatic graphs, Large minimal sets which force arithmetic progressions, The micro-world of cographs, Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four, Probabilistic methods, Proper orientation of cacti, Coloring, sparseness and girth, Fractional Turan's theorem and bounds for the chromatic number, Compactness and finite equivalence of infinite digraphs, Induced subgraphs of graphs with large chromatic number. I. Odd holes, Reducing graph coloring to clique search, Some theorems concerning the star chromatic number of a graph, Fuzzy intersection graphs, The degree distribution of the random multigraphs, Representing orders on the plane by translating convex figures, More results on Ramsey-Turán type problems, On some conjectures of Graffiti, Applications of edge coloring of multigraphs to vertex coloring of graphs, Graphs with bounded tree-width and large odd-girth are almost bipartite, Dualities and dual pairs in Heyting algebras, Independence number and vertex-disjoint cycles, The number of dependent arcs in an acyclic orientation, Bare canonicity of representable cylindric and polyadic algebras, Paths with two blocks in \(n\)-chromatic digraphs, The fractional chromatic number of Zykov products of graphs, Inequalities for the chromatic numbers of graphs, Extending the Gyárfás-Sumner conjecture, Biclique covers and partitions, Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs, The distribution of the maximum degree of a random graph, Unavoidable tournaments, Tree-chromatic number, The critical number of dense triangle-free binary matroids, On semigroups of graph endomorphisms, Classes of graphs with small rank decompositions are \(\chi \)-bounded, Rainbow numbers for graphs containing small cycles, Local and global colorability of graphs, Astral graphs (threshold graphs), scale-free graphs and related algorithmic questions, Degree sequences of random graphs, On the coverings of graphs, A few remarks on Ramsey--Turán-type problems, Random half-integral polytopes, Integer sequence discovery from small graphs, Spanning cycles in regular matroids without small cocircuits, Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences, 3-colorability and forbidden subgraphs. I: Characterizing pairs, Randomly colouring graphs (a combinatorial view), On sparse graphs with given colorings and homomorphisms., Critically partitionable graphs. II, Colouring edges with many colours in cycles, Colouring graphs when the number of colours is almost the maximum degree, 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs., Graphs without large triangle free subgraphs, Excluding cycles with a fixed number of chords, On the chromatic number of \(H\)-free graphs of large minimum degree, Reorientations of covering graphs, Coloring intersection graphs of \(x\)-monotone curves in the plane, Computing independent sets in graphs with large girth, Trees, ladders and graphs, Co-2-plex vertex partitions, A separation theorem in property testing, Obligatory subsystems of triple systems, On the interval of strong partial clones of Boolean functions containing \(\mathrm{Pol}(\{(0, 0), (0, 1), (1, 0)\})\), On the chromatic number of \((P_{5},K_{2,t})\)-free graphs, Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree, The maximum and minimum degree of the random \(r\)-uniform \(r\)-partite hypergraphs, Locally planar graphs are 5-choosable, Note on robust critical graphs with large odd girth, Triangle-free graphs whose independence number equals the degree, On cubical graphs, Online coloring graphs with high girth and high odd girth, Chromatic number and girth, Restricted Ramsey configurations, On an upper bound of the graph's chromatic number, depending on the graph's degree and density, Random graphs and covering graphs of posets, Local convergence of random graph colorings, Colouring lattices, Asymptotic lower bounds for Ramsey functions, Survey sampling in graphs, On classes of relations and graphs determined by subobjects and factorobjects, Chromatic number, girth and maximal degree, A short proof of the existence of highly chromatic hypergraphs without short cycles, Ramsey-type theorems, Clique numbers of graphs and irreducible exact \(m\)-covers of the integers, Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences, Ramsey numbers and an approximation algorithm for the vertex cover problem, Edge-decompositions of highly connected graphs into paths, On \(k\)-chromatically connected graphs, Partitioning graphs into complete and empty graphs, Elements of a theory of computer simulation. I, An uncountably chromatic triple system, Infinite generalized friendship graphs, What must and what need not be contained in a graph of uncountable chromatic number?, Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices, Around quasidiagonal operators, Complexity of diagrams, Restricted frame graphs and a conjecture of Scott, Probabilistic methods in coloring and decomposition problems, Note on a Ramsey-Turán type problem, Coloring graphs with locally few colors, Near optimal colourability on hereditary graph families, Graphs of large chromatic number, Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of \(P_4\), Triangle-free graphs and forbidden subgraphs, Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case, Phase transitions in discrete structures, Lower bounds for the chromatic numbers of distance graphs with large girth, Total domination in regular graphs, Tree-width dichotomy, Best and random approximation of a convex body by a polytope, Computing first and second fuzzy Zagreb indices of linear and multiacyclic hydrocarbons, Induced subgraphs of graphs with large chromatic number. XI. Orientations, The fractional chromatic number of generalized cones over graphs, Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs, Trees contained in every orientation of a graph, On the chromatic number of \(2 K_2\)-free graphs, Tough Ramsey graphs without short cycles, Degree sequence and independence in \(K(4)\)-free graphs, Generalized signed graphs of large girth and large chromatic number, On the chromatic number of some \(P_5\)-free graphs, Bispindles in strongly connected digraphs with large chromatic number, An intersection theorem for four sets, Ramsey-nice families of graphs, On the chromatic numbers of rational spaces, Finitely axiomatizable quasivarieties of graphs, Axiomatisability and hardness for universal Horn classes of hypergraphs, Smallest \(C_{2 \ell + 1}\)-critical graphs of odd-girth \(2 k + 1\), Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions, Uniquely \(D\)-colourable digraphs with large girth. II: Simplification via generalization, Tree index of uncertain graphs, Ramsey type properties of ideals, A note on chromatic number and induced odd cycles, Bispindle in strongly connected digraphs with large chromatic number, Triangle packings and transversals of some \(K_{4}\)-free graphs, Online graph exploration: New results on old and new algorithms, On graphs with a large chromatic number that contain no small odd cycles, Caterpillars in Erdős-Hajnal, Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size, On a Frankl-Rödl theorem and its geometric corollaries, A brief history of Tarskian algebraic logic with new perspectives and innovations, Chromatic number and subtrees of graphs, On operations preserving semi-transitive orientability of graphs, Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs, On nowhere dense graphs, Generalised Ramsey numbers for two sets of cycles, New construction of graphs with high chromatic number and small clique number, Coloring Hasse diagrams and disjointness graphs of curves, Constraints, MMSNP and expander relational structures, Coloring graphs without short cycles and long induced paths, Characterization of forbidden subgraphs for bounded star chromatic number, A note on chromatic number of (cap, even hole)-free graphs, Relatively small counterexamples to Hedetniemi's conjecture, Hedetniemi's conjecture is asymptotically false, Folding list of graphs obtained from a given graph, Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, Hat chromatic number of graphs, A dualistic approach to bounding the chromatic number of a graph, Subdivisions of four blocks cycles in digraphs with large chromatic number, A better upper bound on the chromatic number of (cap, even-hole)-free graphs, A small set in a large parallelepiped., The effect of local majority on global majorityin connected graphs, On forbidden induced subgraphs for \(K_{1, 3}\)-free perfect graphs, Mycielski type constructions for hypergraphs associated with fractional colorings, Distance graphs with large chromatic numbers and small clique numbers, One problem on geometric Ramsey numbers, Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions, Toughness in graphs -- a survey, Counterexamples to Hedetniemi's conjecture, A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function, Extension of Gyárfás-Sumner conjecture to digraphs, Graph partitions with prescribed patterns, Obstructions for three-coloring graphs without induced paths on six vertices, Chromatic numbers of distance graphs without short odd cycles in rational spaces, VC-dimension and Erdős-Pósa property, On the variety generated by completions of representable relation algebras, Conditional chromatic numbers with forbidden cycles, Dold's theorem from viewpoint of strong compatibility graphs, The line analog of Ramsey numbers, Another analog of Ramsey numbers, Degree multiplicities and independent sets in \(K_ 4\)-free graphs, Notes on tree- and path-chromatic number, Note on Hedetniemi's conjecture and the Poljak-Rödl function, Extremal problems for sets forming Boolean algebras and complete partite hypergraphs, Separating tree-chromatic number from path-chromatic number, A coloring problem, Arity hierarchies, On three blocks paths \(P (k, l, r)\), Compactness results in extremal graph theory, From graphs to ortholattices and equivariant maps, Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture, Nearly bipartite graphs with large chromatic number, Counterexamples to Borsuk's conjecture with large girth, Subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number, In absence of long chordless cycles, large tree-width becomes a local phenomenon, A hierarchy of randomness for graphs, Density via duality., From \(\chi\)- to \(\chi_p\)-bounded classes, Immersion and clustered coloring, On the complexity of unfrozen problems, Distance labeling schemes for \(K_4\)-free bridged graphs, A note on a conjecture of Wu, Xu and Xu, High girth hypergraphs with unavoidable monochromatic or rainbow edges, Homotopy types of the Hom complexes of graphs
