Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz
For a graph G, let (G) denote its chromatic number and (G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of (G)= (G) over all n-vertex graphs G. A famous conjecture of Haj os from 1961 states that (G) (G) for every graph G. That is, H(n) 1 for all posit...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2012
|
| Online Access: | http://hdl.handle.net/1721.1/71176 |
| _version_ | 1826195914033725440 |
|---|---|
| author | Fox, Jacob Lee, Choongbum Sudakov, Benny |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Lee, Choongbum Sudakov, Benny |
| author_sort | Fox, Jacob |
| collection | MIT |
| description | For a graph G, let (G) denote its chromatic number and (G) denote the order of the largest
clique subdivision in G. Let H(n) be the maximum of (G)= (G) over all n-vertex graphs G.
A famous conjecture of Haj os from 1961 states that (G) (G) for every graph G. That is,
H(n) 1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd}os
and Fajtlowicz further showed by considering a random graph that H(n) cn1=2= log n for some
absolute constant c > 0. In 1981 they conjectured that this bound is tight up to a constant factor
in that there is some absolute constant C such that (G)= (G) Cn1=2= log n for all n-vertex
graphs G. In this paper we prove the Erd}os-Fajtlowicz conjecture. The main ingredient in our
proof, which might be of independent interest, is an estimate on the order of the largest clique
subdivision which one can nd in every graph on n vertices with independence number . |
| first_indexed | 2024-09-23T10:17:50Z |
| format | Article |
| id | mit-1721.1/71176 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:17:50Z |
| publishDate | 2012 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/711762019-05-17T08:32:44Z Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz Fox, Jacob Lee, Choongbum Sudakov, Benny Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Fox, Jacob For a graph G, let (G) denote its chromatic number and (G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of (G)= (G) over all n-vertex graphs G. A famous conjecture of Haj os from 1961 states that (G) (G) for every graph G. That is, H(n) 1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd}os and Fajtlowicz further showed by considering a random graph that H(n) cn1=2= log n for some absolute constant c > 0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that (G)= (G) Cn1=2= log n for all n-vertex graphs G. In this paper we prove the Erd}os-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can nd in every graph on n vertices with independence number . National Science Foundation (U.S.) (NSF grant DMS-110118) National Science Foundation (U.S.) (CAREER award DMS-0812005) United States-Israel Binational Science Foundation 2012-06-20T14:32:19Z 2012-06-20T14:32:19Z 2011 Article http://purl.org/eprint/type/JournalArticle 0209-9683 1439-6912 http://hdl.handle.net/1721.1/71176 Fox, Jacob, Choongbum Lee and Benny Sudakov. "Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz." Combinatorica 32 (1) (January 2012) p. 111-123. OPEN_ACCESS_POLICY en_US http://dx.doi.org/10.1007/s00493-012-2709-9 Combinatorica Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Fox, Jacob Lee, Choongbum Sudakov, Benny Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz |
| title | Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz |
| title_full | Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz |
| title_fullStr | Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz |
| title_full_unstemmed | Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz |
| title_short | Chromatic number, clique subdivisions, and the conjectures of Hajos and Erdos-Fajtlowicz |
| title_sort | chromatic number clique subdivisions and the conjectures of hajos and erdos fajtlowicz |
| url | http://hdl.handle.net/1721.1/71176 |
| work_keys_str_mv | AT foxjacob chromaticnumbercliquesubdivisionsandtheconjecturesofhajosanderdosfajtlowicz AT leechoongbum chromaticnumbercliquesubdivisionsandtheconjecturesofhajosanderdosfajtlowicz AT sudakovbenny chromaticnumbercliquesubdivisionsandtheconjecturesofhajosanderdosfajtlowicz |