Three short proofs in graph theory
From MaRDI portal
Publication:1223319
DOI10.1016/0095-8956(75)90089-1zbMath0322.05142OpenAlexW1987745187MaRDI QIDQ1223319
Publication date: 1975
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(75)90089-1
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)
Related Items (59)
Optimal three-dimensional orthogonal graph drawing in the general position model. ⋮ Noncontextual coloring of orthogonality hypergraphs ⋮ The linzertorte problem, or a unified approach to painting, baking and weaving ⋮ On \(r\)-dynamic coloring of graphs ⋮ Spotting Trees with Few Leaves ⋮ Spotting Trees with Few Leaves ⋮ \(\Delta \)-list vertex coloring in linear time ⋮ On approximation properties of the Independent set problem for degree 3 graphs ⋮ Brooks' Theorem and Beyond ⋮ Improved approximations for maximum independent set via approximation chains ⋮ Graph \(r\)-hued colorings -- a survey ⋮ On essential components and critical sets of a graph ⋮ On constructive methods in the theory of colour-critical graphs ⋮ On the hardness of computing span of subcubic graphs ⋮ Graphs with $\chi=\Delta$ Have Big Cliques ⋮ Partitioning into degenerate graphs in linear time ⋮ Optimizing concurrency under Scheduling by Edge Reversal ⋮ Four proofs of the directed Brooks' theorem ⋮ Symmetric set coloring of signed graphs ⋮ Brooks' theorem for generalized dart graphs ⋮ Efficient approximation algorithms for bandwidth consecutive multicolorings of graphs ⋮ Max-leaves spanning tree is APX-hard for cubic graphs ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ Non-separating induced cycles in graphs ⋮ The chromatic number of a signed graph ⋮ The many facets of upper domination ⋮ Brooks-type theorem for \(r\)-hued coloring of graphs ⋮ A unified proof of Brooks' theorem and Catlin's theorem ⋮ COLORING ALGORITHMS ON SUBCUBIC GRAPHS ⋮ Dichotomy for Coloring of Dart Graphs ⋮ Directed star decompositions of directed multigraphs ⋮ A characterization of the prime graphs of solvable groups. ⋮ Improved distributed \(\Delta\)-coloring ⋮ Price of anarchy for graph coloring games with concave payoff ⋮ A short proof of Brooks’ Theorem for vertex arboricity ⋮ An exact algorithm for MAX-CUT in sparse graphs ⋮ Greed is good: Approximating independent sets in sparse and bounded-degree graphs ⋮ Maximum weight edge-constrained matchings ⋮ Partitioning a graph into degenerate subgraphs ⋮ On the probabilistic minimum coloring and minimum \(k\)-coloring ⋮ Brooks' theorem via the Alon-Tarsi theorem ⋮ On a Lovász-type lemma, applied to Brooks' theorem for list-colouring ⋮ Algorithmic bounds for the chromatic number† ⋮ A different short proof of Brooks' theorem ⋮ Vertex-Coloring with Star-Defects ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ An extension of Tutte's 1-factor theorem ⋮ Representations of families of triples over \(GF(2)\) ⋮ Upper Domination: Complexity and Approximation ⋮ A characterisation of some 2-connected graphs and a comment on an algorithmic proof of Brooks' theorem ⋮ Coloring Graphs with Constraints on Connectivity ⋮ Differential approximation algorithms for some combinatorial optimization problems ⋮ Saturated Simple and 2-simple Topological Graphs with Few Edges ⋮ A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios ⋮ Approximation algorithms for vertex happiness ⋮ A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs ⋮ Efficient bounds for the stable set, vertex cover and set packing problems ⋮ Regular factors in nearly regular graphs ⋮ Construction methods for gaussoids
This page was built for publication: Three short proofs in graph theory
