Chromatically optimal rigid graphs

DOI10.1016/0095-8956(89)90039-7zbMath0677.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)

Related Items

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

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