The chromatic number of the product of two 4-chromatic graphs is 4
From MaRDI portal
Publication:1063620
DOI10.1007/BF02579374zbMath0575.05028OpenAlexW2095076239WikidataQ64356946 ScholiaQ64356946MaRDI QIDQ1063620
Mohamed H. El-Zahar, Norbert W. Sauer
Publication date: 1985
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02579374
Related Items (59)
On 3-chromatic distance-regular graphs ⋮ The chromatic number of the product of 14-chromatic graphs can be 13 ⋮ Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings ⋮ On multiplicative graphs and the product conjecture ⋮ Square-free graphs are multiplicative ⋮ Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers ⋮ Shannon capacity and the categorical product ⋮ Lattices arising in categorial investigations of Hedetniemi's conjecture ⋮ Multiplicativity of acyclic digraphs ⋮ Coloring graph products---a survey ⋮ Neighborhood complexes, homotopy test graphs and an application to coloring of product graphs ⋮ On multichromatic numbers of widely colorable graphs ⋮ Vector coloring the categorical product of graphs ⋮ Incidence hypergraphs: the categorical inconsistency of set-systems and a characterization of quiver exponentials ⋮ Acyclic coloring of products of digraphs ⋮ On optimizing edge connectivity of product graphs ⋮ Hedetniemi's conjecture and dense Boolean lattices ⋮ Critical graphs without triangles: an optimum density construction ⋮ The fractional version of Hedetniemi's conjecture is true ⋮ The \(k\)-independence number of direct products of graphs and Hedetniemi's conjecture ⋮ On 3-colorings of direct products of graphs ⋮ Relatively small counterexamples to Hedetniemi's conjecture ⋮ Hedetniemi's conjecture is asymptotically false ⋮ On idomatic partitions of direct products of complete graphs ⋮ 𝜔-categorical structures avoiding height 1 identities ⋮ Minimal definable graphs of definable chromatic number at least three ⋮ A complexity problem for Borel graphs ⋮ On the restricted homomorphism problem ⋮ A simple proof of the multiplicativity of directed cycles of prime power length ⋮ Hedetniemi's conjecture and adjoint functors in thin categories ⋮ Multiplicative posets ⋮ Achromatic numbers and graph operations ⋮ Fractional chromatic numbers of cones over graphs ⋮ Generic automorphisms and graph coloring ⋮ On topological relaxations of chromatic conjectures ⋮ Counterexamples to Hedetniemi's conjecture ⋮ A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function ⋮ Independence and coloring properties of direct products of some vertex-transitive graphs ⋮ Coloring the Cartesian sum of graphs ⋮ Note on Hedetniemi's conjecture and the Poljak-Rödl function ⋮ Multiplicativity of acyclic local tournaments ⋮ Borel chromatic numbers ⋮ \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture ⋮ Hedetniemi's Conjecture and Strongly Multiplicative Graphs ⋮ A note on the Poljak-Rödl function ⋮ Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers ⋮ Chromatic Ramsey numbers ⋮ Chromatic numbers and products ⋮ My Top 10 Graph Theory Conjectures and Open Problems ⋮ Multiplicative graphs and semi-lattice endomorphisms in the category of graphs ⋮ On inverse powers of graphs and topological implications of Hedetniemi's conjecture ⋮ Unique list-colourability and the fixing chromatic number of graphs ⋮ Density via duality. ⋮ The categorical product of two 5-chromatic digraphs can be 3-chromatic ⋮ The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable ⋮ Coloring the Cartesian Sum of Graphs ⋮ Homomorphisms to oriented cycles ⋮ Applications of Hajós‐Type Constructions to the Hedetniemi Conjecture ⋮ Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices
Cites Work
This page was built for publication: The chromatic number of the product of two 4-chromatic graphs is 4
