scientific article; zbMATH DE number 3043302
From MaRDI portal
zbMath0027.26403MaRDI QIDQ5782525
Publication date: 1941
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
The \(m\)-degenerate chromatic number of a digraph, Coloring signed graphs using DFS, On \(r\)-dynamic coloring of graphs, Chromatic number of \(P_5\)-free graphs: Reed's conjecture, Graph polynomials and paintability of plane graphs, A lower bound on the independence number of a graph in terms of degrees and local clique sizes, On bipartization of cubic graphs by removal of an independent set, \(\Delta \)-list vertex coloring in linear time, Some generalizations of theorems on vertex coloring, Graph homomorphisms into the five-cycle, List homomorphisms of graphs with bounded degrees, \([r,s,t\)-colorings of graphs], Spectral radii of graphs with given chromatic number, \([r,s,t\)-chromatic numbers and hereditary properties of graphs], Highly irregular m-chromatic graphs, Recursive coloration of countable graphs, Inequalities between the domination number and the chromatic number of a graph, Applications of edge coloring of multigraphs to vertex coloring of graphs, On constructive methods in the theory of colour-critical graphs, On the chromatic number of integral circulant graphs, Independent sets in \(\{\text{claw}, K_4 \}\)-free 4-regular graphs, Domination and total domination in cubic graphs of large girth, Finite groups whose prime graphs are regular., The complexity of changing colourings with bounded maximum degree, The \((p,q)\)-total labeling problem for trees, Graphs with chromatic number close to maximum degree, Are there any good digraph width measures?, Equitable \(\Delta\)-coloring of graphs, Brooks' theorem for generalized dart graphs, Spectra of uniform hypergraphs, A matroid analogue of a theorem of Brooks for graphs, The chromatic number of a signed graph, Hamiltonian degree conditions which imply a graph is pancyclic, A comparison of bounds for the chromatic number of a graph, On graphs with no induced subdivision of \(K_4\), Chromatic optimisation: Limitations, objectives, uses, references, Distributed colorings for collision-free routing in sink-centric sensor networks, A property tester for tree-likeness of quartet topologies, Randomly colouring graphs (a combinatorial view), Improvement on Brooks' chromatic bound for a class of graphs, Ore's conjecture on color-critical graphs is almost true, Colouring graphs when the number of colours is almost the maximum degree, On degree sums of a triangle-free graph, Coloring a graph with \(\Delta-1\) colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker, A unified proof of Brooks' theorem and Catlin's theorem, The complexity of the empire colouring problem, The symbiotic relationship of combinatorics and matrix theory, A nonlinear lower bound on the practical combinational complexity, Partition into cliques for cubic graphs: Planar case, complexity and approximation, Supersaturation problem for color-critical graphs, An introduction to the discharging method via graph coloring, The complexity of some graph colouring problems, Degree choosable signed graphs, Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree, Characterizing 4-critical graphs with Ore-degree at most seven, Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number, Some upper bounds for the product of the domination number and the chromatic number of a graph, Bounded vertex colorings of graphs, Covering the cliques of a graph with vertices, \([r,s,t\)-coloring of trees and bipartite graphs], Acyclically 3-colorable planar graphs, Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs, On preserving full orientability of graphs, Variable neighborhood search for extremal graphs. 22. Extending bounds for independence to upper irredundance, Some results on Reed's conjecture about \(\omega ,\Delta \), and \(\chi \) with respect to \(\alpha \), Grundy number and products of graphs, Chromatic numbers of infinite graphs, Excess in critical graphs, Boundary properties of graphs for algorithmic graph problems, On the Ramsey numbers for stars versus complete graphs, Brooks' theorem via the Alon-Tarsi theorem, Degree bounds for linear discrepancy of interval orders and disconnected posets, Some simplified NP-complete graph problems, Rainbow graph splitting, An extension of Brooks' theorem to n-degenerate graphs, On graphs whose least eigenvalue exceeds \(-1-\sqrt2\), 2-distance vertex-distinguishing index of subcubic graphs, Covering the vertex set of a graph with subgraphs of smaller degree, Every graph \(G\) is Hall \(\Delta(G)\)-extendible, Hadwiger's conjecture for 3-arc graphs, A bound on the chromatic number of a graph, A short proof of Catlin's extension of Brooks' theorem, Edge-coloring of 3-uniform hypergraphs, The chromatic number of 5-valent circulants, Chromatic coloring with a maximum color class, Another bound on the chromatic number of a graph, Colouring problems, On the choice number of complete multipartite graphs with part size four, Approximation algorithm for maximum edge coloring, \(H\)-coloring degree-bounded (acyclic) digraphs, Linear time self-stabilizing colorings, A graph colouring model for assigning a heterogeneous workforce to a given schedule, On critical subgraphs of colour-critical graphs, Extension problems with degree bounds, Precoloring extension for 2-connected graphs with maximum degree three, On list critical graphs, Efficient bounds for the stable set, vertex cover and set packing problems, Independence in graphs with maximum degree four, Small embeddings of partial directed triple systems and partial triple systems with even \(\lambda\), Regular independent sets, Some Ramsey-Type Numbers and the Independence Ratio, Painting squares in \(\Delta^2-1\) shades, On approximation properties of the Independent set problem for degree 3 graphs, Approximation of Constraint Satisfaction via local search, Digraphs and Variable Degeneracy, Plongements lipschitziens dans ${\bbfR}\sp n$, Zig-zag facial total-coloring of plane graphs, Some graph theoretical aspects of generalized truncations, On three outer-independent domination related parameters in graphs, A greedy algorithm for the social golfer and the Oberwolfach problem, Unnamed Item, The proper vertex-disconnection of graphs, A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph, Note on 4-coloring 6-regular triangulations on the torus, Optimal Packet-Oblivious Stable Routing in Multi-hop Wireless Networks, Extremal decompositions for Nordhaus-Gaddum theorems, Coloring (P5,gem) $({P}_{5},\text{gem})$‐free graphs with Δ−1 ${\rm{\Delta }}-1$ colors, Combinatorics. Abstracts from the workshop held January 1--7, 2023, Partitions of hypergraphs under variable degeneracy constraints, The chromatic number of {ISK4, diamond, bowtie}‐free graphs, Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration, A note on \(\Delta\)-critical graphs, LARGE SIGNED SUBSET SUMS, Partitioning into degenerate graphs in linear time, Graph and hypergraph colouring via nibble methods: a survey, Optimizing concurrency under Scheduling by Edge Reversal, Large cliques in graphs with high chromatic number, Generalized DP-colorings of graphs, Four proofs of the directed Brooks' theorem, Yet another proof of Brooks' theorem, The list version of the Borodin-Kostochka conjecture for graphs with large maximum degree, Relating the independence number and the dissociation number, Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number, Symmetric set coloring of signed graphs, Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph, Nordhaus–Gaddum problem in terms of G-free coloring, The high order spectrum of a graph and its applications in graph colouring and clique counting, Dirac's theorem on chordal graphs implies Brooks' theorem, A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions, Graph folding and chromatic number, Coloring \(\{ P 2 \cup P 3 , \operatorname{house} \} \)-free graphs with \(\Delta - 1\) colors, Strengthening Brooks' chromatic bound on \(P_6\)-free graphs, Coloring hammer-free graphs with \(\Delta - 1\) colors, Partitioning of a graph into induced subgraphs not containing prescribed cliques, A Brooks-like result for graph powers, Odd coloring of sparse graphs and planar graphs, Two Remarks on Eventown and Oddtown Problems, Flip graphs for infinite type surfaces, Unnamed Item, Brooks-type theorem for \(r\)-hued coloring of graphs, Kempe equivalence of colourings of cubic graphs, Rainbow neighbourhood number of graphs, On percolation and ‐hardness, Unnamed Item, Unnamed Item, A short proof of Brooks’ Theorem for vertex arboricity, Distance Laplacian eigenvalues and chromatic number in graphs, Unnamed Item, Unnamed Item, Unnamed Item, On group chromatic number of graphs, Partition the vertices of a graph into one independent set and one acyclic set, Tough graphs and Hamiltonian circuits. (Reprint), Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Conditional colorings of graphs, Hadwiger number and chromatic number for near regular degree sequences, Unnamed Item, Hard coloring problems in low degree planar bipartite graphs, Some Topics in Graph Theory, A local epsilon version of Reed's conjecture, Simultaneous graph parameters: factor domination and factor total domination, A different short proof of Brooks' theorem, Cost Minimisation in Multi-interface Networks, On the maximum spectral radius of multipartite graphs, Vertex partition of hypergraphs and maximum degenerate subhypergraphs, Kempe equivalence of colourings of cubic graphs, Large Independent Sets in Triangle-Free Planar Graphs, On Tuza's conjecture for triangulations and graphs with small treewidth, APX-hardness and approximation for the \(k\)-burning number problem, APX-hardness and approximation for the \(k\)-burning number problem, A nonlinear lower bound on the practical combinational complexity, On Tuza's conjecture for triangulations and graphs with small treewidth, Multiple Domination, On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size, On the total coloring of certain graphs, Recursive families of graphs, Square-Free Graphs with No Six-Vertex Induced Path, Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks, On the Independence Number of Graphs with Maximum Degree 3, Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable, Tough graphs and Hamiltonian circuits., Relative Cayley graphs of finite groups, Extended Gallai's Theorem, Turán Graphs, Stability Number, and Fibonacci Index, A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs, On the \(b\)-dominating coloring of graphs, Fractional Chromatic Number, Maximum Degree, and Girth, A brief history of edge-colorings – with personal reminiscences, Upper bounds for the chromatic number of a graph, On r-hued coloring of product graphs, Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring, Algorithmic complexity of list colorings, The choice number versus the chromatic number for graphs embeddable on orientable surfaces, Independent sets of maximum weight in (\(p,q\))-colorable graphs., Optimal three-dimensional orthogonal graph drawing in the general position model., Graph polynomials and group coloring of graphs, Chromatic properties of the Pancake graphs, On decision and optimization (\(k\),\(l\))-graph sandwich problems, On the fractional dimension of partially ordered sets, Stable routing scheduling algorithms in multi-hop wireless networks, Point partition numbers: decomposable and indecomposable critical graphs, A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs, The colour theorems of Brooks and Gallai extended, On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs, Spanning trees with pairwise nonadjacent endvertices, Independent sets in regular graphs, Bounds on the dynamic chromatic number of a graph in terms of its chromatic number, Going wide with the 1-2-3 conjecture, On equitable coloring of bipartite graphs, Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques, Edge density and independence ratio in triangle-free graphs with maximum degree three, On bounding the difference between the maximum degree and the chromatic number by a constant, A geometric multigrid preconditioning strategy for DPG system matrices, Graph \(r\)-hued colorings -- a survey, Bounds on eigenvalues and chromatic numbers, Complexity of the improper twin edge coloring of graphs, The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs, Strengthening \((a,b)\)-choosability results to \((a,b)\)-paintability, Finding independent sets in \(K_4\)-free 4-regular connected graphs, Domination versus independent domination in graphs of small regularity, Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem, Maximizing the number of independent sets of fixed size in connected graphs with given independence number, Weighted improper colouring, Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines, A proof of Tomescu's graph coloring conjecture, Upper transversals in hypergraphs, Domination parameters of a graph and its complement, On the number of touching pairs in a set of planar curves, A new lower bound on the number of edges in colour-critical graphs and hypergraphs, A note on relaxed equitable coloring of graphs, Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems, Relations between the lower domination parameters and the chromatic number of a graph., Generalized hypergraph coloring, 3-colorability and forbidden subgraphs. I: Characterizing pairs, The complexity of the proper orientation number, On \(k\)-domination and \(j\)-independence in graphs, On a conjecture of Mohar concerning Kempe equivalence of regular graphs, On the \(k\)-planar local crossing number, Distance-two colourings of Barnette graphs, An immune algorithm with stochastic aging and Kullback entropy for the chromatic number problem, An upper bound for the chromatic number of line graphs, On the role of 3s for the 1--2--3 conjecture, Corrigendum to: ``A local epsilon version of Reed's conjecture, A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs, Tree-based unrooted nonbinary phylogenetic networks, Partitioning sparse graphs into an independent set and a forest of bounded degree, A Brooks type theorem for the maximum local edge connectivity, Eigenvalue bounds for the signless \(p\)-Laplacian, Maximum weight edge-constrained matchings, New potential functions for greedy independence and coloring, Fractionally total colouring \(G_{n,p}\), Domination in graphs of minimum degree at least two and large girth, Chromatic numbers of layered graphs with a bounded maximal clique, Dynamic proper colorings of a graph, Measurable versions of Vizing's theorem, Remarks on dynamic monopolies with given average thresholds, Star edge-coloring of graphs with maximum degree four, A hypocoloring model for batch scheduling, Partitioning a graph into degenerate subgraphs, The complexity of the Hajós calculus for planar graphs, Graph coloring, minimum-diameter partitioning, and the analysis of confusion matrices, On a Lovász-type lemma, applied to Brooks' theorem for list-colouring, Maximum independent sets near the upper bound, On 3-colouring of graphs with short faces and bounded maximum vertex degree, An improved upper bound on neighbor expanded sum distinguishing index, Improved lower bounds on the number of edges in list critical and online list critical graphs, Coloring of pseudocubic graphs in three colors, Equitable coloring of some convex polytope graphs, Inverting the Turán problem with chromatic number, Borodin-Kostochka's conjecture on \((P_5,C_4)\)-free graphs, Minimum fill-in: inapproximability and almost tight lower bounds, Differential approximation algorithms for some combinatorial optimization problems, ``Global graph problems tend to be intractable, On \(r\)-hued list coloring of \(K_4 ( 7 )\)-minor free graphs, A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios, The subchromatic number of a graph, Coloring graphs with sparse neighborhoods, A new Turán-type theorem for cliques in graphs, Approximation algorithms for vertex happiness, Graphes cubiques d'indice trois, graphes cubiques isochromatiques, graphes cubiques d'indice quatre, Introduction to reconfiguration, Colour-critical graphs with few edges, DP-degree colorable hypergraphs, On the number of nonisomorphic orientable regular embeddings of complete graphs, A strengthening of Brooks' theorem, A note on coloring vertex-transitive graphs, The independence number of graphs in terms of degrees, Distributed coloring algorithms for triangle-free graphs, 4-edge-coloring graphs of maximum degree 3 in linear time, Hardness of approximation of the discrete time-cost tradeoff problem, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
