Brooks' theorem

Complete graphs need one more color than their maximum degree. They and the odd cycles are the only exceptions to Brooks' theorem.

In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.

The theorem is named after R. Leonard Brooks, who published a proof of it in 1941.[1] A coloring with the number of colors described by Brooks' theorem is sometimes called a Brooks coloring[2] or a Δ-coloring.[3]

Formal statement

For any connected undirected graph G with maximum degree Δ, the chromatic number of G is at most Δ, unless G is a complete graph or an odd cycle, in which case the chromatic number is Δ + 1.[1]

Proof

László Lovász gives a simplified proof of Brooks' theorem. If the graph is not biconnected, its biconnected components may be colored separately and then the colorings combined. If the graph has a vertex v with degree less than Δ, then a greedy coloring algorithm that colors vertices farther from v before closer ones uses at most Δ colors. This is because at the time that each vertex other than v is colored, at least one of its neighbors (the one on a shortest path to v) is uncolored, so it has fewer than Δ colored neighbors and has a free color. When the algorithm reaches v, its small number of neighbors allows it to be colored. Therefore, the most difficult case of the proof concerns biconnected Δ-regular graphs with Δ ≥ 3. In this case, Lovász shows that one can find a spanning tree such that two nonadjacent neighbors u and w of the root v are leaves in the tree. A greedy coloring starting from u and w and processing the remaining vertices of the spanning tree in bottom-up order, ending at v, uses at most Δ colors. For, when every vertex other than v is colored, it has an uncolored parent, so its already-colored neighbors cannot use up all the free colors, while at v the two neighbors u and w have equal colors so again a free color remains for v itself.[4]

Extensions

A more general version of the theorem applies to list coloring: given any connected undirected graph with maximum degree Δ that is neither a clique nor an odd cycle, and a list of Δ colors for each vertex, it is possible to choose a color for each vertex from its list so that no two adjacent vertices have the same color. In other words, the list chromatic number of a connected undirected graph G never exceeds Δ, unless G is a clique or an odd cycle.[5]

For certain graphs, even fewer than Δ colors may be needed. Δ − 1 colors suffice if and only if the given graph has no Δ-clique, provided Δ is large enough.[6] For triangle-free graphs, or more generally graphs in which the neighborhood of every vertex is sufficiently sparse, O(Δ/log Δ) colors suffice.[7]

The degree of a graph also appears in upper bounds for other types of coloring; for edge coloring, the result that the chromatic index is at most Δ + 1 is Vizing's theorem. An extension of Brooks' theorem to total coloring, stating that the total chromatic number is at most Δ + 2, has been conjectured by Mehdi Behzad and Vizing. The Hajnal–Szemerédi theorem on equitable coloring states that any graph has a (Δ + 1)-coloring in which the sizes of any two color classes differ by at most one.

Algorithms

A Δ-coloring, or even a Δ-list-coloring, of a degree-Δ graph may be found in linear time.[8] Efficient algorithms are also known for finding Brooks colorings in parallel and distributed models of computation.[9]

Notes

References

  • Alon, Noga; Krivelevich, Michael; Sudakov, Benny (1999), "Coloring graphs with sparse neighborhoods", Journal of Combinatorial Theory, Series B, 77 (1): 73–82, doi:10.1006/jctb.1999.1910
  • Brooks, R. L. (1941), "On colouring the nodes of a network", Mathematical Proceedings of the Cambridge Philosophical Society, 37 (2): 194–197, Bibcode:1941PCPS...37..194B, doi:10.1017/S030500410002168X, S2CID 209835194.
  • Grable, David A.; Panconesi, Alessandro (2000), "Fast distributed algorithms for Brooks–Vizing colourings", Journal of Algorithms, 37: 85–120, doi:10.1006/jagm.2000.1097, S2CID 14211416.
  • Hajnal, Péter; Szemerédi, Endre (1990), "Brooks coloring in parallel", SIAM Journal on Discrete Mathematics, 3 (1): 74–80, doi:10.1137/0403008.
  • Karloff, H. J. (1989), "An NC algorithm for Brooks' theorem", Theoretical Computer Science, 68 (1): 89–103, doi:10.1016/0304-3975(89)90121-7.
  • Lovász, L. (1975), "Three short proofs in graph theory", Journal of Combinatorial Theory, Series B, 19 (3): 269–271, doi:10.1016/0095-8956(75)90089-1.
  • Panconesi, Alessandro; Srinivasan, Aravind (1995), "The local nature of Δ-coloring and its algorithmic applications", Combinatorica, 15 (2): 255–280, doi:10.1007/BF01200759, S2CID 28307157.
  • Reed, Bruce (1999), "A strengthening of Brooks' theorem", Journal of Combinatorial Theory, Series B, 76 (2): 136–149, doi:10.1006/jctb.1998.1891.
  • Skulrattanakulchai, San (2006), "Δ-List vertex coloring in linear time", Information Processing Letters, 98 (3): 101–106, doi:10.1016/j.ipl.2005.12.007.
  • Vizing, V. G. (1976), "Vertex colorings with given colors", Diskret. Analiz. (in Russian), 29: 3–10.

Read other articles:

Species of bird Armenian gull Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Order: Charadriiformes Family: Laridae Genus: Larus Species: L. armenicus Binomial name Larus armenicusButurlin, 1934 Synonyms[2] Larus cachinnans armenicus The Armenian gull (Larus armenicus) is a large gull found in the Caucasus and the Middle East. It was formerly classified as a subspecies of the ...

 

Faro Monumental de La Serena Monumento Histórico de Chile Faro Monumental de La Serena en 2022.IdentificaciónNúmero internacional G1900.5Número nacional 002UbicaciónPaís  ChileMunicipio La Serena (Chile)Localidad La SerenaUbicación Chile ChileCoordenadas 29°54′20″S 71°16′28″O / -29.905583333333, -71.274361111111Información generalLuz Luz negraFases 5 segundosAlcance 20Altura focal 28 mAltura soporte 25Autor de proyecto Armad...

 

Бунде Bunde —  сільська громада  — Вид Бунде Герб Координати: 53°11′ пн. ш. 7°16′ сх. д. / 53.183° пн. ш. 7.267° сх. д. / 53.183; 7.267 Країна  Німеччина Земля Нижня Саксонія Район Лер Площа  - Повна 121 км² Висота над р.м. 2 м  Населенн

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يونيو 2023) هذه مقالة غير مراجعة. ينبغي أن يزال هذا القالب بعد أن يراجعها محرر مغاير للذي أنشأها؛ إذا لزم الأمر فيجب أن توسم المقالة بقوالب الصيانة المناسبة. يمكن أيضاً تق

 

هايلاند هيلز     الإحداثيات 41°26′49″N 81°31′28″W / 41.4469°N 81.5244°W / 41.4469; -81.5244  تقسيم إداري  البلد الولايات المتحدة[1]  التقسيم الأعلى مقاطعة كاياهوغا، أوهايو  خصائص جغرافية  المساحة 5.089563 كيلومتر مربع5.092629 كيلومتر مربع (1 أبريل 2010)  ارتفاع 334 متر...

 

Untuk kegunaan lain, lihat Atlantik.Samudra AtlantikKoordinat0°N 25°W / 0°N 25°W / 0; -25Koordinat: 0°N 25°W / 0°N 25°W / 0; -25[1]Terletak di negaraDaftar negara, pelabuhanArea permukaan106.460.000 km2 (41.100.000 sq mi)[2][3]Atlantik Utara: 41.490.000 km2 (16.020.000 sq mi), Atlantik Selatan 40.270.000 km2 (15.550.000 sq mi)[4]Kedalaman rata-rata3.646 m (...

Christian school in Mercer County, New Jersey, United States A major contributor to this article appears to have a close connection with its subject. It may require cleanup to comply with Wikipedia's content policies, particularly neutral point of view. Please discuss further on the talk page. (January 2022) (Learn how and when to remove this template message) The Wilberforce SchoolAddress75 Mapleton Road, Building TwoPrinceton, Mercer County, New Jersey 08540United StatesCoordinates40°21′32

 

Rettungskapsel eines B-58-Bombers Eine Rettungskapsel, manchmal auch Fluchtkapsel, ist ein Rettungsmittel und kann Teil der Notfallausrüstung eines Fahrzeugs oder eines Habitats sein. Sie schließt ihre Insassen während einer Evakuierung ein und schützt sie vor den Umgebungsbedingungen. Dies kann eine grundsätzlich lebensfeindliche Umgebung wie Unterwasser oder im Weltraum sein. Sie kann aber auch durch Begleiterscheinungen der Ereignisse entstanden sein, die eine Evakuierung notwendig ma...

 

Film company specializing in educational films Coronet FilmsFounded1934; 89 years ago (1934)Defunct1997; 26 years ago (1997)[1]FateClosedOwnerPhoenix Learning Group, Inc. Coronet Films (also known as Coronet Instructional Media Inc.) was an American producer and distributor of documentary shorts shown in public schools, mostly in the 16mm format, from the 1940s through the 1980s (when the videocassette recorder replaced the motion picture projector ...

This article is about the Australian television station. For other uses, see NWS (disambiguation). For the network currently owned by Southern Cross Austereo and a former Nine Network affiliate, see 10 (Southern Cross Austereo). Television station in Adelaide, South AustraliaNWSAdelaide, South AustraliaChannelsDigital: 8 (VHF)Virtual: 9BrandingNineProgrammingAffiliationsNineOwnershipOwnerNine Entertainment Co.(Channel 9 South Australia Pty Ltd)HistoryFirst air date5 September 1959;&#...

 

Mountain in British Columbia, Canada Anarchist MountainView of Osoyoos Lake from near the summit of the hill-climb on Highway 3 to Anarchist MountainHighest pointElevation1,491 m (4,892 ft)[1]Prominence186 m (610 ft)[1]ListingMountains of British ColumbiaCoordinates49°02′18″N 119°20′10″W / 49.03833°N 119.33611°W / 49.03833; -119.33611[2]GeographyAnarchist MountainBritish Columbia, Canada DistrictSim...

 

Таблиця Менделєєва опублікована в 1871 році з прочерками на місці припущених, але ще не відкритих елементів. Відкриті хімічні елементи (кін. 2016 р.)Коротка форма періодичної системи елементів — один із способів зображення періодичної системи хімічних елементів, що сх...

SMK Bina Insan Mulia BandungInformasiDidirikan2004AkreditasiAkreditasi 'A' & ISO 9001:2008Kepala SekolahAkhmad Hartoko SC,SE.M.MJurusan atau peminatanFarmasi, Informatika (Rekayasa Perangkat Lunak, Teknik Komputer & Jaringan), Manajemen Bisnis (Penjualan, Akuntansi, Adm.Perkantoran)AlamatLokasiJl. Tubagus Ismail no.13, Bandung, Jawa Barat, IndonesiaTel./Faks.(022) 2045 4122Situs webwww.smkbim.sch.idMotoMotoFriendly School, Be Smart, Be Proffesional Sekolah Menengah Kejuruan ...

 

Brazilian firm MovileTypePrivateIndustryInternetComputer softwareTelecoms equipmentFounded1998 (1998)FounderFabricio Bloisi & Eduardo HenriqueHeadquartersCampinas, SP, BrazilNumber of employees1600Websitemovile.com Movile is a local Brazilian firm headquartered in Campinas, Brazil. Movile operates in the segments of food ordering and delivery, ticketing, and logistics. It has had mixed success till now with the bet on food delivery maturing (iFood) while other bets still at nascent s...

 

Tari Serampang 12 Tari Serampang 12 adalah tari tradisional yang berasal dari Kabupaten Deli Serdang, Sumatera Utara. Gerakan tari Serampang 12 merupakan perpaduan dari gerak Melayu Deli dengan dua belas macam gerakan yang dimiliki. Tari serampang 12 memiliki tempo cepat. Sejarah Sauti, pencipta Tari Serampang 12 Guru Sauti, pencipta tari Serampang 12 Pencipta daripada tari Serampang 12 ialah Guru Sauti. Beliau lahir pada tahun 1903 di Pantai Cermin Sumatra Timur (lokasi kini berada di Pesisi...

American government official (born 1952) Kim HolmesUnited States Assistant Secretary of State for International Organization AffairsIn officeNovember 21, 2002 – May 1, 2005PresidentGeorge W. BushPreceded byDavid WelchSucceeded byKristen Silverberg Personal detailsBorn1952 (age 70–71)NationalityAmericanPolitical partyRepublicanAlma materUniversity of Central FloridaGeorgetown University Kim R. Holmes (born 1952)[1] is an author and former American diplomat and Ass...

 

PUSAT PENDIDIKAN LATIHAN KORPS BRIMOB POLRILambang Pusdik BrimobDibentuk10 Juni 1954NegaraIndonesiaCabang Kepolisian Negara Republik IndonesiaTipe unitPendidikan latihan Kejuruan Brimob PolriBagian dariLemdiklat PolriMarkas KomandoJl. Raya Watukosek Gempol, Pasuruan, Jawa TimurMotoPadma Widya CaktiBaret BIRU GELAP Situs webwww.korpsBrimob.polri.go.idTokohKapusdikKombes Pol. Heri Sulesmono, S.I.K.WakapusdikAKBP. Agung Anggoro, S.I.K., M.H. Pusat Pendidikan Korps Brimob Polri (Pusdik ...

 

Municipality in Taiwan This article is about the special municipality formerly known as Taoyuan County. For former county-administered Taoyuan City, see Taoyuan District. For the district in Kaohsiung, see Taoyuan District, Kaohsiung. This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Taoyuan, Taiwan – news · newspapers · ...

1973 album by Neil Innes How Sweet to Be an IdiotStudio album by Neil InnesReleased1973 (UK)RecordedMarch – July 1973StudioChipping Norton Studio, OxfordshireGenrePop/rockLength37:56LabelUnited ArtistsProducerNeil InnesNeil Innes chronology How Sweet to Be an Idiot(1973) The Rutland Weekend Songbook(1976) Professional ratingsReview scoresSourceRatingAllmusic[1] Re-Cycled Vinyl BluesStudio album by Neil InnesReleased1994 (UK)Recorded1973GenrePop/rockLabelEMIProducerNeil Innes...

 

Commune in Occitanie, France Commune in Occitania, FranceAlairacCommuneAn aerial view of Alairac Coat of armsLocation of Alairac AlairacShow map of FranceAlairacShow map of OccitanieCoordinates: 43°11′06″N 2°14′29″E / 43.185°N 2.2414°E / 43.185; 2.2414CountryFranceRegionOccitaniaDepartmentAudeArrondissementCarcassonneCantonCarcassonne-3IntercommunalityCarcassonne AggloGovernment • Mayor (2020–2026) Marc Adivèze[1]Area116.37 ...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!