Chromatically optimal rigid graphs

DOI10.1016/0095-8956(89)90039-7zbMATH Open0677.05031OpenAlexW2039470646MaRDI QIDQ1123199

Vojtěch Rödl, Jaroslav Nešetřil

Publication date: 1989

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(89)90039-7

zbMATH Keywords

chromatic numberrigid graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Symmetric relations (undirected graphs) with given semigroups
• Every finite graph is a full subgraph of a rigid graph
• On a technique for representing semigroups as endomorphism semigroups of graphs with given properties
• Universal graphs without large bipartite subgraphs
• High Chromatic Rigid Graphs II
• Universal graphs and universal functions
• On chromatic number of graphs and set-systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (22)

Dualities and algebras with a near-unanimity term ⋮ Coloring, sparseness and girth ⋮ Generalized signed graphs of large girth and large chromatic number ⋮ Homomorphically full graphs ⋮ Fractal property of the graph homomorphism order ⋮ Partitions of graphs into cographs ⋮ NP for Combinatorialists ⋮ On Finite Maximal Antichains in the Homomorphism Order ⋮ On digraph coloring problems and treewidth duality ⋮ Forbidden lifts (NP and CSP for combinatorialists) ⋮ On the order of countable graphs ⋮ Graphs of large chromatic number ⋮ Tension continuous maps -- their structure and applications ⋮ Many Facets of Dualities ⋮ Colouring, constraint satisfaction, and complexity ⋮ On sparse graphs with given colorings and homomorphisms. ⋮ The core of a graph ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ CSP duality and trees of bounded pathwidth ⋮ Unnamed Item ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Cuts and bounds

This page was built for publication: Chromatically optimal rigid graphs