Coloring, sparseness, and girth

Noga Alon, Alexandr Kostochka, Benjamin Reiniger, Douglas B. West, Xuding Zhu

Type: Preprint

Publication Date: 2014-01-01

Citations: 2

DOI: https://doi.org/10.48550/arxiv.1412.8002

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Coloring the square of a sparse graph $G$ with almost $Δ(G)$ colors	2015	Matthew Yancey
+	Improved bounds for coloring locally sparse hypergraphs	2020	Fotis Iliopoulos
+	$K_r$-saturated Graphs and the Two Families Theorem	2023	Asier Calbet
+ PDF Chat	A note on the multicolor size-Ramsey numbers of connected graphs	2024	Louis DeBiasio
+	Ramsey goodness of bounded degree trees	2016	Igor Balla Alexey Pokrovskiy Benny Sudakov
+	Sparse hypergraphs: new bounds and constructions	2017	Gennian Ge Chong Shangguan
+	Sparse H -Colourable Graphs of Bounded Maximum Degree	2004	Xuding Zhu Hossein Hajiabolhassan
+ PDF Chat	Sparse Hypergraphs with Applications to Coding Theory	2020	Chong Shangguan Itzhak Tamo
+	Effective bounds for induced size-Ramsey numbers of cycles	2023	Domagoj Bradač Nemanja Draganić Benny Sudakov
+	Sparse graphs with bounded induced cycle packing number have logarithmic treewidth	2022	Marthe Bonamy Édouard Bonnet Hugues Déprés Louis Esperet Colin Geniet Claire Hilaire Stéphan Thomassé Alexandra Wesolek
+ PDF Chat	Sparse hypergraphs with low independence number	2015	Jeff Cooper Dhruv Mubayi
+	New results for MaxCut in $H$-free graphs	2021	Stefan Glock Oliver Janzer Benny Sudakov
+	$K_r$-Saturated Graphs and the Two Families Theorem	2024	Asier Calbet
+	Ramsey numbers of sparse hypergraphs	2007	David Conlon Jacob Fox Benny Sudakov
+	Girth, minimum degree, independence, and broadcast independence	2018	Stéphane Bessy Dieter Rautenbach
+	Coloring the square of a sparse graph $G$ with almost $\Delta(G)$ colors	2015	Matthew Yancey
+ PDF Chat	Star colouring of bounded degree graphs and regular graphs	2022	M. A. Shalu Cyriac Antony
+	Effective bounds for induced size-Ramsey numbers of cycles	2023	Domagoj Bradač Nemanja Draganić Benny Sudakov
+	Choosability with union separation	2015	Mohit Kumbhat Kevin Moss Derrick Stolee
+	Choosability with union separation	2015	Mohit Kumbhat Kevin Moss Derrick Stolee

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	Subdivisions of oriented cycles in digraphs with large chromatic number	2018	Nathann Cohen Frédéric Havet William Lochet Nicolas Nisse

Works Cited by This (7)

Action	Title	Year	Authors
+	Ahypergraph-free construction of highly chromatic graphs without short cycles	1989	Igor Kříž
+ PDF Chat	On chromatic number of graphs and set systems	1973	Paul Erdös A. Hajnal B. Rothchild
+ PDF Chat	On the Number of Edges in Colour-Critical Graphs and Hypergraphs	2000	Alexandr Kostochka Michael Stiebitz
+	On the degrees of the vertices of a directed graph	1965	S. L. Hakimi
+	Graph Theory and Probability	2009	P. Erdős
+ PDF Chat	Choosability with Separation of Complete Multipartite Graphs and Hypergraphs	2013	Zoltán Füredi Alexandr Kostochka Mohit Kumbhat
+	Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number	1999	A. V. K Ostochka