New bounds on clique-chromatic numbers of Johnson graphs

DOI10.1016/j.dam.2020.01.015zbMath1442.05068OpenAlexW3001464251MaRDI QIDQ2192124

Mikhail M. Koshelev, Andrei M. Raigorodskii

Publication date: 29 June 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2020.01.015

zbMATH Keywords

Ramsey numbersJohnson graphsclique-chromatic numbers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Related Items

Coverings of planar and three-dimensional sets with subsets of smaller diameter, Random cyclic triangle-free graphs of prime order, Interview with Andrei Raigorodskii, On the independence number and the chromatic number of generalized preferential attachment models, Exact modularity of line graphs of complete graphs, New lower bound on the modularity of Johnson graphs, On stability of the independence number of a certain distance graph, Estimate of the number of edges in subgraphs of a Johnson graph, Chromatic numbers of distance graphs without short odd cycles in rational spaces, Lower bounds on the clique-chromatic numbers of some distance graphs, Bounds on Borsuk numbers in distance graphs of a special type, Covering planar sets, New Turán type bounds for Johnson graphs, Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique-transversal sets of line graphs and complements of line graphs
• Perfect graphs of arbitrarily large clique-chromatic number
• Intersection theorems with geometric consequences
• Families of sets with no matchings of sizes 3 and 4
• The Borsuk partition problem: the seventieth anniversary
• On the independence numbers of some distance graphs with vertices in \(\{-1, 0, 1\}^n\)
• On lower bounds for the chromatic number of spheres
• Clique chromatic numbers of intersection graphs
• A remark on lower bounds for the chromatic numbers of spaces of small dimension with metrics \(\ell_1\) and \(\ell_2\)
• The number of edges in induced subgraphs of some distance graphs
• Counterexamples to Borsuk's conjecture with large girth
• On small \(n\)-uniform hypergraphs with positive discrepancy
• Panchromatic 3-colorings of random hypergraphs
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• Around Borsuk's hypothesis
• Clique-Coloring Circular-Arc Graphs
• A counterexample to Borsuk’s conjecture
• Clique-coloring some classes of odd-hole-free graphs
• Clique coloring of dense random graphs
• Coloring the Maximal Cliques of Graphs
• Partition‐free families of sets
• Colouring clique-hypergraphs of circulant graphs