Harmonious coloring

Harmonious coloring of the complete 7-ary tree with 3 levels using 12 colors. The harmonious chromatic number of this graph is 12. Any fewer colors will result in a color pair appearing on more than one pair of adjacent vertices. Moreover, by Mitchem's Formula, χH(T7,3) = ⌈(3/2)(7+1)⌉ = 12.

In graph theory, a harmonious coloring is a (proper) vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. It is the opposite of the complete coloring, which instead requires every color pairing to occur at least once. The harmonious chromatic number χH(G) of a graph G is the minimum number of colors needed for any harmonious coloring of G.

Every graph has a harmonious coloring, since it suffices to assign every vertex a distinct color; thus χH(G) ≤ |V(G)|. There trivially exist graphs G with χH(G) > χ(G) (where χ is the chromatic number); one example is any path of length > 2, which can be 2-colored but has no harmonious coloring with 2 colors.

Some properties of χH(G):

where Tk,3 is the complete k-ary tree with 3 levels. (Mitchem 1989)

Harmonious coloring was first proposed by Harary and Plantholt (1982). Still very little is known about it.

See also

References

Read other articles:

Menggapai Mimpi

Menggapai MimpiAlbum studio karya Dearly Dave SompieDirilis2 Juli 2008GenrePopLabelSony BMG IndonesiaKronologi Dearly Dave Sompie Tribute To Tonny Koeswoyo(2006)Indonesian IdolTribute To Tonny Koeswoyo2006 Menggapai Mimpi (2008) Menggapai Mimpi merupakan sebuah album musik pertama karya Dirly Sompie. Dirilis pada tahun 2008. Lagu utamanya di album ini ialah Sampai Ke Ujung Dunia. Daftar lagu Let's Get The Beat Tak Pernah Rela Sampai Ke Ujung Dunia Hujan Bumi Berhenti Berputar Kemenangan H...

 

الدوري المونتينيغري الممتاز 2007–08

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (نوفمبر 2019) الدوري المونتينيغري الممتاز 2007–08 تفاصيل الموسم الدوري المونتينيغري الممتاز  النسخة 2  البلد الجبل ...

 

List of acts of the Parliament of the United Kingdom from 2002

Part of a series onBritish law Acts of Parliament of the United Kingdom Year      1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 ...

Jethro Tull (band)

British rock band For the English agricultural pioneer after whom the band is named, see Jethro Tull (agriculturist). Jethro TullJethro Tull live in Hamburg in 1973Background informationOriginBlackpool, Lancashire, EnglandGenres Progressive rock folk rock hard rock blues rock Years active1967–20112017–presentLabelsIslandRepriseWarner Bros.ChrysalisEagleFuel 2000EMIInside Out MusicSpinoffs Blodwyn Pig Wild Turkey Members Ian Anderson David Goodier John O'Hara Scott Hammond Jack Clark Past ...

 

BMW Seri 1 (E87)

BMW 1 SeriesInformasiProdusenBMWMasa produksiMei 2004–2011 (E87)[1]2007–2012 (E81)2007–sekarang (E82)2007–sekarang (E88)PerakitanLeipzig, JermanRegensburg, JermanPerancangChristopher Chapman (E87: 2001)[2][3]Bodi & rangkaBentuk kerangkacoupe 2 pintu (E82)konvertibel 2 pintu (E88)hatchback 3 pintu (E81)hatchback 5 pintu (E87)Tata letakFR layoutKronologiPendahuluBMW KompakPenerusF20, F21 Generasi pertama BMW Seri 1 adalah mobil keluarga kecil yang diprod...

 

Federated Malay States

British protectorate and part of British Malaya Not to be confused with Federation of Malaya or Unfederated Malay States. This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) 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: Federated Malay State...

Panait Istrati

Romanian writer 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: Panait Istrati – news · newspapers · books · scholar · JSTOR (January 2016) (Learn how and when to remove this message) Panait Istrati (1927) Panait Istrati (Romanian: [panaˈit isˈtrati]; sometimes rendered as Panaït Istrati; August 1...

 

Juliusz Słowacki

Juliusz SłowackiBiographieNaissance 4 septembre 1809KremenetsDécès 3 avril 1849 (à 39 ans)Ancien 1er arrondissement de ParisSépulture Cimetière de Montmartre, cathédrale du WawelNationalité polonaiseFormation Université de VilniusActivités Poète, dramaturge, écrivain, traducteur, diplomate, philosophePériode d'activité 1830-1849Famille Słowacki-Leliwa (d)Père Euzebiusz Słowacki (d)Mère Salomea Slowacka (d)Autres informationsA travaillé pour Université de VilniusMembre...

 

Karad Airport

Airport in Maharashtra, India Karad AirportIATA: noneICAO: VA1MSummaryAirport typePublicOwnerM.A.D.C.OperatorM.A.D.C.ServesKaradLocationKarad, Maharashtra, India Elevation AMSL1,890 ft / 576 mCoordinates17°17′09″N 074°09′29″E / 17.28583°N 74.15806°E / 17.28583; 74.15806MapKarad AirportRunways Direction Length Surface ft m 10/28 4,200 1,280 Paved World Aero Data[usurped] Karad Airport (ICAO: VA1M) is in the Satara district of Maharashtra state...

123Movies

Online illegal movie streaming site network 123Movies / GoMoviesType of siteOnline file hosting indexAvailable inEnglishCountry of originVietnamArea servedWorldwideEditors(Vietnamese-based)[1][2]RevenueAdvertisingCommercialYesRegistrationOptionalUsers98 million at peak[3]Launchedest. 2015–2016[a]Current statusOffline (clones and copy sites are still available)[2]Content licenseUnlicensed[4] 123Movies, GoMovies, GoStream, MeMovie...

 

WTA Argentine Open 1978 - Singolare

WTA Argentine Open 1978Singolare Sport Tennis Vincitore Caroline Stoll Finalista Emilse Rapponi Punteggio 6-3, 6-2 Tornei Singolare Singolare   Doppio Doppio Voce principale: WTA Argentine Open 1978. Il singolare del torneo di tennis WTA Argentine Open 1978, facente parte del WTA Tour 1978, ha avuto come vincitrice Caroline Stoll che ha battuto in finale Emilse Rapponi 6-3, 6-2. Indice 1 Teste di serie 2 Tabellone 2.1 Legenda 2.2 Finale 2.3 Parte alta 2.4 Parte bassa 3 Collegamenti este...

 

Josh Ruffels

English association football player Josh Ruffels Ruffels playing for Oxford United in 2013Personal informationFull name Joshua Andrew Bernard Ruffels[1]Date of birth (1993-10-23) 23 October 1993 (age 30)[2]Place of birth Oxford, EnglandHeight 5 ft 10 in (1.78 m)[3]Position(s) Left-back[4]Team informationCurrent team Huddersfield TownNumber 3Youth career0000–2011 Coventry CitySenior career*Years Team Apps (Gls)2011–2013 Coventry City 1 (0...

Виді Бог, виді Сотворитель

Коляда «Ой видить Бог, видить творець» у виконанні Яблунівського хору «Просвіта» «Виді Бог, виді Сотворитель» (у деяких варіантах: «Видить же Бог, видить Творець»[1])  — українська апокрифічна колядка християнського цилку. Уперше опублікована в «Богогласнику» в 1790...

 

David Magradze

Georgian poet and politician David MagradzeBorn28 June 1962Tbilisi, Georgian SSR, Soviet UnionCitizenshipSoviet, GeorgianSignature David Dato Magradze (Georgian: დავით დათო მაღრაძე; born 28 June 1962) is a Georgian poet and politician. He is the author of lyrics of the current national anthem of Georgia, in use since 2004. Born to the family of the writer and literary scholar Elguja Magradze in Tbilisi, Magradze is a philologist by education trained at the ...

 

Examiner Newspaper Group

Examiner Newspaper Group, Inc.Houston Community Newspapers Examiner Newspaper Group officesParent companyHouston ChronicleStatusActiveFounded2001; 23 years ago (2001)FoundersGeorge Boehme and Edwin HenryCountry of originUnited StatesPublication typesBellaire Examiner, Memorial Examiner, River Oaks Examiner, and West University ExaminerNonfiction topicsLocal newsOwner(s)Hearst CorporationOfficial websitewww.yourexaminernews.com The Examiner Newspaper Group, Inc. consists of a...

Automated Transfer Vehicle

Automated Transfer Vehicle, awalnya Ariane Transfer Vehicle atau ATV, adalah pesawat ruang angkasa kargo sekali pakai yang dikembangkan oleh European Space Agency (ESA). ATV menyediakan Stasiun Luar Angkasa Internasional (ISS) dengan propelan, air, udara, muatan, dan eksperimen. ATV juga dapat reboosted stasiun ke orbit yang lebih tinggi. Lima ATV, Jules Verne, Johannes Kepler, Edoardo Amaldi, Albert Einstein, dan Georges Lemaitre telah diluncurkan, pertama pada Maret 2008. Pada tanggal 2 Ap...

 

John Rillie

Australian basketball player and coach John RillieRillie with the Perth Wildcats in 2022Perth WildcatsPositionHead coachLeagueNBLPersonal informationBorn (1971-11-04) 4 November 1971 (age 52)Toowoomba, Queensland, AustraliaListed height195 cm (6 ft 5 in)Listed weight85 kg (187 lb)Career informationHigh schoolHarristown State(Toowoomba, Queensland)College Tacoma CC (1991–1992) Gonzaga (1992–1995) NBA draft1995: undraftedPlaying career1995–2010PositionShootin...

 

Maria Gonzaga, Duchess of Montferrat

Regent of Mantua Maria GonzagaRegent of MantuaBorn29 July 1609MantuaDied14 August 1660(1660-08-14) (aged 51)MantuaSpouse Charles Gonzaga, Duke of Nevers ​ ​(m. 1627; died 1631)​IssueMaria GonzagaCharles II, Duke of Mantua and MontferratEleonora, Holy Roman EmpressNamesMaria GonzagaHouseGonzagaFatherFrancesco GonzagaMotherMargaret of Savoy Maria Gonzaga or Maria of Mantua (29 July 1609 – 14 August 1660) was a reigning duchess of Montferrat...

ويكيبيديا الفريولية

ويكيبيديا الفريوليةالشعارمعلومات عامةموقع الويب fur.wikipedia.org (الفريولية) نوع الموقع نسخة بلغة من ويكيبيديا التأسيس 25 يناير 2005 الجوانب التقنيةاللغة الفريولية ترخيص المحتوى رخصة المشاع الإبداعي الملزِمة بالنسب لمؤلِّف العمل وبالترخيص بالمثل غير القابلة للإلغاء 3.0 — رخصة جن...

 

Olahraga elektronik

The International, sebuah turnamen tahunan dari Dota 2. Pada tahun 2011, Valve mengundang 16 tim Dota terbaik di dunia, hadiah yang diberikan dalam pertandingan ini yaitu 1,6 juta dollar (sekarang setara dengan Rp21 miliar).[1] Olahraga elektronik (bahasa Inggris: electronic sports, e-sports, esports) merupakan suatu istilah untuk kompetisi permainan video pemain jamak, umumnya antara para pemain profesional. Aliran permainan video yang biasanya dihubungkan dengan olahraga elektro...