Towards the Albertson conjecture

MaRDI QIDQ976729zbMATH OpenFDO

Authors János Barát, Géza Tóth

Publication date 16 June 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.0413, https://eudml.org/doc/223129, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r73.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic numbercrossing number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: Albertson conjectured that if a graph $G$ has chromatic number $r$ then its crossing number is at least as much as the crossing number of $K_r$. Albertson, Cranston, and Fox verified the conjecture for $rle12$. We prove the statement for $rle16$.

Review text

Summary: Albertson conjectured that if a graph \(G\) has chromatic number \(r\), then the crossing number of \(G\) is at least as large as the crossing number of \(K_r\), the complete graph on \(r\) vertices. \textit{M.O. Albertson}, \textit{D.W. Cranston}, and \textit{J. Fox} [``Crossings, colorings, and cliques, Electron. J. Comb. 16, No.\,1, Research Paper R45 (2009; Zbl 1182.05035)] verified the conjecture for \(r \geqslant 12\). In this paper we prove it for \(r\leqslant 16\).

Recommendations

• On Alspach's conjecture
• On the Alspach conjecture
• A note on Alperin's conjecture
• On the conjecture of Alon-Tarsi
• Alder's conjecture
• On the Casas-Alvero conjecture
• On a generalization of Albert's theorem
• scientific article; zbMATH DE number 4152671
• The Alon-Tarsi conjecture: a perspective on the main results
• On a conjecture of Alon

Cited in

(7)

• On the Alspach conjecture
• The crossing number of the cone of a graph
• Remarks on a conjecture of Barát and Tóth
• The crossing number of the cone of a graph
• A survey of graphs with known or bounded crossing numbers
• Colorings, cliques and relaxations of planarity
• Immersions and Albertson's conjecture

This page was built for publication: Towards the Albertson conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976729)