Infallsfärgning

I grafteorin innebär färgläggningen i allmänhet tilldelning av etiketter till hörn , kanter eller ytor i en graf . Incidensfärgningen är en speciell grafmärkning där varje incidens av en kant med en vertex tilldelas en färg under vissa begränsningar .

Definitioner

Nedan G betecknar en enkel graf med icke-tom vertexuppsättning ( icke-tom) V ( G ), kantmängd E ( G ) och maximal grad Δ( G ).

Definition. En incidens definieras som ett par ( v , e ) där $v\in V(G)$ är en slutpunkt för $e\in E(G).$ Med enkla ord säger man att vertex v är infallande mot kanten e . Två incidenser ( v , e ) och ( u , f ) sägs vara intilliggande eller närliggande om något av följande gäller:

v = u , e ≠ f
e = f , v ≠ u
e = { v , u }, f = { u , w } och v ≠ w .

Exempel på angränsande/intilliggande incidenter. * ovanför kanten e närmast vertex v anger incidens (v,e).

Definition. Låt I ( G ) vara mängden av alla förekomster av G. En incidensfärgning av G är en funktion $c:I(G)\to \mathbb {N}$ som tar distinkta värden på intilliggande incidenser (vi använder den förenklade notationen c ( v , u ) används istället för c (( v , e )).) Det minsta antalet färger som behövs för infallsfärgning av en graf G är känt som det kromatiska infallstalet eller incidensfärgningstalet för G , representerat av $\chi _{i}(G).$ Denna notation introducerades av Jennifer J. Quinn Massey och Richard A. Brualdi 1993.

Infallsfärgning av en Petersen-graf

Historia

Begreppet incidensfärgning introducerades av Brualdi och Massey 1993 som avgränsade det i termer av Δ( G ). Inledningsvis upptäcktes det kromatiska antalet träd, kompletta tvådelade grafer och kompletta grafer. De förmodade också att alla grafer kan ha en incidensfärgning med användning av Δ( G ) + 2 färger (Incidensfärgningsförmodan - ICC). Denna gissning motbevisades av Guiduli, som visade att incidensfärgningskonceptet är ett riktat stjärnarboricitetsfall, introducerat av Alon och Algor. Hans motexempel visade att incidensens kromatiska tal är högst Δ( G ) + O(log Δ( G )).

Chen et al. hittade incidensen kromatiska antalet banor , fläktar, cykler , hjul, komplett tredelad graf och lägga till kanthjul. Några år senare, Shiu et al. visade att denna gissning är sann för vissa kubiska grafer som kubiska Hamiltonska grafer. Han visade att i fallet med en ytterplanar graf av maximal grad 4, är det kromatiska talet för incidensen inte 5. Gränserna för det kromatiska antalet incidens för olika grafklasser är nu utrett.

Grundläggande resultat

Förslag.

\chi _{i}(G)\geq \Delta (G)+1.

Bevis. Låt v vara spetsen med maximal grad Δ i G . Låt $e_{1},e_{2},\ldots ,e_{\Delta }$ vara de kanter som infaller med vertex v . Betrakta $e_{1}=\{v,w\}.$ Vi kan se att varje par av Δ + 1 förekomster, det vill säga $(v,e_{1}),(v,e_{2}),\ldots ,(v,e_{\Delta }),(w,e_{ 1})$ är granne. Därför måste dessa förekomster färgas med distinkta färger.

Bindningen uppnås av träd och kompletta grafer:

Om G är en komplett graf med minst två hörn så är $\chi _{i}(G)=\Delta (G)+1.$
Om G är ett träd med minst två hörn så är $\chi _{i}(G)=\Delta (G)+1.$

Huvudresultaten bevisades av Brualdi och Massey (1993). Shiu, Sun och Wu har föreslagit vissa nödvändiga villkor för att grafen ska uppfylla $\chi _{i}(G)=\Delta (G)+1.$

$\chi _{i}(G)\leq 2\Delta (G).$
Det kromatiska incidenstalet för den kompletta tvådelade grafen $K_{m,n}$ med m ≥ n ≥ 2, är m + 2.
$\chi _{i}(C_{n})\leq 4$ och $\chi _{i}(C_{ 3n})=3.$

Incidensfärgning av vissa grafklasser

Maskor

Flera algoritmer introduceras för att ge infallsfärgning av maskor som fyrkantiga maskor , bikakemaskor och hexagonala maskor. Dessa algoritmer är optimala. För varje mesh kan infallsfärgerna göras i den linjära tiden med minst färger. Det har visat sig att ∆( G ) + 1 färger krävs för infallsfärgning av kvadratiska maskor, bikakemaskor och sexkantiga maskor.

Incidensens kromatiska tal för ett kvadratnät är 5.
Det kromatiska incidenstalet för ett hexagonalt nät är 7.
Förekomstens kromatiska tal för ett bikakenät är 4.

Halin-grafer

Chen, Wang och Pang bevisade att om G är en Halin-graf med ∆( G ) > 4 så $\chi _{i}(G)=\Delta ( G)+1.$ För Halin-grafer med ∆( G ) = 3 eller 4 visade Jing-Zhe Qu att $\chi _{i}(G)$ var 5 respektive 6. Huruvida infallsfärgningstalet för Halin-grafer med låg grad är Δ( G ) + 1 är fortfarande ett olöst problem.

Shiu och Sun visade att varje kubisk Halin-graf förutom $K_{4}$ har en infallsfärgning med Δ( G ) + 2 färger. Su, Meng och Guo utökade detta resultat till alla pseudo-Halin-grafer.

Om Halin-grafen G innehåller ett träd T , då $\chi _{i}(G^{2})\leq \ Delta (T^{2})+\Delta (T)+8.$

k-degenererade grafer

DL Chen, PCB Lam och WC Shiu hade gissat att det kromatiska incidenstalet för en kubisk graf G är högst ∆( G ) + 2. De bevisade detta för vissa kubiska grafer som Hamiltonska kubiska grafer. Baserat på dessa resultat studerade MH Dolama, E. Sopena och X. Zhu (2004) de grafklasser för vilka $\chi _{i}(G)$ avgränsas av ∆( G ) + c där c är någon fast konstant. En graf sägs vara k -genererad om för varje subgraf H av G , den minsta graden av H är högst k .

Incidens kromatiskt antal k -degenererade grafer G är som mest ∆( G ) + 2 k − 1.
Incidens kromatiskt antal K ₄ mindre fria grafer G är som mest ∆( G ) + 2 och det bildar en snäv gräns.
Incidensens kromatiska tal för en plan graf G är som mest ∆( G ) + 7.

Outerplanar grafer

Betrakta en ytterplanär graf G med skuren vertex v så att G – v är föreningen av $H_{1}$ och $H_{2}$ . Låt $G_{1}$ (resp. $G_{2}$ ) vara den inducerade subgrafen på vertex v och hörn av $H_{1}$ (resp. $H_{2}$ ). Då $\chi _{i}(G)$ maximum av $\chi _{i}(G_{1} ),\chi _{i}(G_{2})$ och $1+d_{G}(v)$ där $d_{G}( v)$ är graden av vertex v i G .

Det kromatiska infallstalet för en ytterplanär graf G är högst ∆( G ) + 2. I fallet med ytterplanära grafer med ∆( G ) > 3 är incidensens kromatiska tal ∆( G ) + 1.

Eftersom ytterplanära grafer är K ₄ -mollfria grafer accepterar de en (Δ + 2, 2)–infallsfärgning. Lösningen för det kromatiska infallstalet för den yttre planära grafen G med Δ( G ) = 3 och 2-kopplad ytterplanargraf är fortfarande en öppen fråga.

Kordringar

Kordringar är varianter av ringnätverk. Användningen av ackordringar i kommunikation är mycket omfattande på grund av dess fördelar gentemot sammankopplingsnätverken med ringtopologi och andra analyserade strukturer såsom maskor, hyperkuber, Cayleys grafer, etc. Arden och Lee föreslog först ackordsringen av grad 3, dvs. , det ringstrukturerade nätverket där varje nod har en extra länk känd som ackord, till någon annan nod i nätverket. Distributed loop-nätverk är ackordringar av grad 4 som är konstruerade genom att lägga till 2 extra ackord vid varje vertex i ett ringnätverk.

Ackordsringen på N noder och ackordslängden d , betecknad med CR ( N , d ), är en graf som definieras som:

{\begin{aligned}V( G)&=\{v_{0},v_{1},\ldots ,v_{N-1}\}\\E(G)&=\{v_{i}v_{j}:ij\equiv 1 ,d{\bmod {N}}\}\end{aligned}}

Dessa grafer studeras på grund av deras tillämpning i kommunikation. Kung-Fu Ding, Kung-Jui Pai och Ro-Yu Wu studerade förekomstens färgning av ackordringar. Flera algoritmer är formulerade för att hitta det kromatiska antalet ackordringar. De viktigaste fynden är:

{\begin{aligned}\chi _{i}(CR(N,2))&={\begin{cases}5&5|N\\6&{\text{annars} }\end{cases}}\\\chi _{i}(CR(N,3))&={\begin{cases}5&5|N\\6&N\equiv 2{\bmod {5}}\end{ fall}}\end{aligned}}

Krafter av cykler

Keaitsuda Nakprasit och Kittikorn Nakprasit studerade incidensfärgning av krafter i cykler, $C_{n}^{k}.$ Om 2 k + 1 ≥ n så är $C_{n}^{k}=K_{n}$ så antag n > 2 k + 1 och skriv:

n=(2k+1)t+r,\quad 1\leq t,\quad 0\leq r\leq 2k.

Deras resultat kan sammanfattas enligt följande:

{\begin{aligned}\chi _{i}(C_{n}^{k})&={\begin{cases}2k+1&r=0\\2k+2&1\leq r\ leq t{\text{ eller }}r=2k\end{cases}}&&k\geq 3\\\chi _{i}(C_{n}^{2})&={\begin{cases}5&5| n\\6&{\text{annars}}\end{cases}}\end{aligned}}

Relationen till förmodan om incidensfärgning ges av observationen att $\Delta (C_{n}^{k})=2k.$

Förhållandet mellan incidenskromatiskt tal och dominansnummer för en graf

Förslag. Låt G vara en enkel sammanhängande graf av ordningen n , storlek m och dominansnummer

\gamma .

Då

\chi _{i}(G)\geq {\tfrac {2m}{n-\gamma }}.

Bevis. Bilda en digraf D ( G ) från graf G genom att dela varje kant av G i 2 bågar i motsatta riktningar. Vi kan se att det totala antalet bågar i D ( G ) är 2 m . Enligt Guiduli är infallsfärgningen av G ekvivalent med korrekt färgning av digrafen D ( G ), där 2 distinkta bågar ${\overrightarrow {uv}}$ och ${\overrightarrow {xy}}$ är angränsande om något av följande villkor gäller: (i) u = x ; (ii) v = x eller y = u . Enligt definitionen av närliggande bågar är en oberoende uppsättning av bågar i D ( G ) en stjärnskog. Därför är en maximal oberoende uppsättning av bågar en maximal stjärnskog . Detta innebär att minst ${\tfrac {2m}{n-\gamma }}$ färgklasser krävs.

Denna relation har använts i stor utsträckning vid karakteriseringen av ( r + 1)-incidens färgbara r -regelbundna grafer. Huvudresultatet på incidensfärgning av r -reguljära grafer är: Om graf G är r-reguljär graf , då $\chi _{i}(G )=\chi _{i}(G^{2})=r+1$ om och endast om V ( G ) är en disjunkt union av r + 1 dominerande mängder .

Intervallinfallsfärgning

Definition. En finit delmängd $A\subset \mathbb {N}$ är ett intervall om och endast om det innehåller alla tal mellan dess minimum och dess maximum.

Definition. Låt c vara en infallsfärgning av G och definiera

A_{c}(v)=\{c(v,e):(v,e)\in I(G)\}.

En intervallinfallsfärgning av G är en infallsfärgning c så att för varje vertex v i G är mängden $A_{c}(v)$ ett intervall. Intervallinfallsfärgningstalet för G är det minsta antalet färger som används för intervallincidensfärgningen av G . Den betecknas med $\chi _{ii}.$ Det är tydligt att ${\displaystyle \chi _{i}(G)\leq \chi _{ii}(G).} Om endast$ χ $\displaystyle \chi _{ii}}-$ färger används för intervallincidensfärgning, då det sägs vara minimalt.

Konceptet med intervallincidensfärgning introducerades av A. Malafiejska, R. Janczewski och M. Malafiejski. De bevisade $\chi _{ii}(G)\leq \Delta (G)$ för tvådelade grafer. I fallet med vanliga tvådelade grafer gäller jämlikhet. Subkubiska tvådelade grafer tillåter en intervallincidensfärgning med fyra, fem eller sex färger. De har också visat att incidens 5-färgbarhet kan bestämmas i linjär tid för tvådelade grafer med ∆( G ) = 4.

Fraktionell infallsfärgning

Bråkversionen av incidensfärgningen introducerades först av Yang 2007. En r -tupelincidens k -färgning av en graf G är tilldelningen av r färger till varje incidens av graf G från en uppsättning k färger så att de intilliggande incidenserna ges osammanhängande uppsättningar av färger. Per definition är det uppenbart att 1-tuppel incidens k -färgning också är en incidens k -färgning.

Det kromatiska talet för bråktalsincidensen för graf G är infimum av bråken ${\tfrac {k}{r}}$ på ett sådant sätt att G medger en r -tupelincidens k -färgning. Fraktionerad incidensfärgning har stora tillämpningar inom flera områden av datavetenskap. Baserat på incidensfärgningsresultat av Guiduli, har Yang bevisat att det kromatiska talet för bråktalsincidensen för en graf som mest är Δ( G ) + 20 log Δ( G ) + 84. Han har också bevisat förekomsten av grafer med bråktalsincidens kromatiskt tal åtminstone Δ( G ) + Ω(log Δ( G )).

Nordhaus–Gaddum ojämlikhet

Låt G vara en graf med n hörn så att $G\neq K_{n},{\overline {K_{n}}}$ där ${\overline { G}}$ betecknar komplementet till G . Då är $n+2\leq \chi _{i}(G)+\chi _{i}({\ överlinje {G}})\leq 2n-1.$ Dessa gränser är skarpa för alla värden på n .

Förekomst färgspel

Incidensfärgningsspelet introducerades först av SD Andres. Det är infallsversionen av vertexfärgningsspelet, där förekomsten av en graf är färgad istället för hörn. Incidensspelets kromatiska tal är den nya parametern definierad som en spelteoretisk analog med incidensens kromatiska tal.

Spelet går ut på att två spelare, Alice och Bob konstruerar en riktig infallsfärgning. Reglerna anges nedan:

Alice och Bob färglägger förekomsten av en graf G med en uppsättning k färger.
De turas om att ge en korrekt färg till en ofärgad förekomst. I allmänhet börjar Alice.
I fallet med en incident som inte kan färgas ordentligt, då vinner Bob.
Om varje förekomst av grafen är korrekt färgad vinner Alice.

Incidensspelets kromatiska nummer för en graf G , betecknad med $i_{g}(G)$ , är det minsta antalet färger som krävs för att Alice ska vinna i ett incidensfärgningsspel. Det förenar idéerna om infallskromatiskt nummer för en graf och spelets kromatiska tal i fallet med en oriktad graf. Andres fick reda på att den övre gränsen för $i_{g}(G)$ i fallet med k -degenererade grafer är 2Δ + 4 k − 2. Denna gräns förbättrades till 2Δ + 3 k − 1 i fallet med grafer där Δ är minst 5 k . Incidensspelets kromatiska antal stjärnor, cykler och tillräckligt stora hjul bestäms också. John Y. Kim (2011) har tagit reda på det exakta kromatiska antalet incidensspel av stora banor och har gett ett korrekt bevis på ett resultat som anges av Andres angående det exakta kromatiska antalet stora hjul för incidensspelet.

Ytterligare länkar

Maydanskiy, M. (2005), "The incidence coloring conjecture for graphs of maximum degree 3" , Discrete Mathematics , vol. 292, s. 131–141 .
Hartke, SG; Helleloid, GT (2012), "Reconstructing a graph from its arc incidence graph", Graphs and Combinatorics , vol. 28, s. 637–652, doi : 10.1007/s00373-011-1073-7 , S2CID 14656326 .
Sun, PK; Shiu, WC (2012), "Invalid proofs on incidence coloring" (PDF) , Discrete Mathematics , vol. 54, s. 107–114 .
Li, D; Liu, M. (2008), "Infallsfärgning av kvadraterna i vissa grafer" , Discrete Mathematics , vol. 308, s. 6575–6580 .
Bonamy, M.; Hocquard, H.; Kerdjoudj, S.; Raspaud, A. (2015), Incidensfärgning av grafer med hög maximal medelgrad , arXiv : 1412.6803 , Bibcode : 2014arXiv1412.6803B .
Hosseini Dolama, M.; Sopena, E. (2005), "Om den maximala genomsnittliga graden och incidensen kromatiskt antal av en graf" (PDF) , Diskret matematik och teoretisk datavetenskap , vol. 7, s. 203–216 .
Shiu, WC; Sun, PK (2006), "Grafer som inte är (∆ + 1)-incidens färgbara med erratum till incidensen kromatiska antalet ytterplanära grafer" ( PDF) . ^{[ död länk ]}
Shiu, WC; Lam, PCP; Chen, DL (2002), "On incidence coloring for some cubic graphs" , Discrete Mathematics , vol. 252, s. 259–266, doi : 10.1016/S0012-365X(01)00457-5 .
Nakprasit, K. (2014), "The strong chromatic index of graphs and subdivisions" , Discrete Mathematics , vol. 317, s. 75–78 .
Ding, KF; Pai, K.J; Chang, JM; Tsaur, R. (2015), "Some results of incidence coloring of generalized Petersen graphs", Intelligent Systems and Applications: Proceedings of the International Computer Symposium (ICS) som hölls i Taichung, Taiwan, 12 december 14, 2014, vol . 274, s. 85–91, doi : 10.3233/978-1-61499-484-8-85 .
Liang, L.; Gao, W. (2010), "Om fraktionerad incidens kromatiskt antal generaliserade teta-grafer", Journal of Chongqing Normal University , vol. 27, s. 36–39 .
Shiu, WC; Lam, PCB; Chen, DL (2002), "Anmärkning om incidensfärgning för vissa kubiska grafer", Discrete Mathematics , vol. 252, s. 259–266 .
Sun, PK; Shiu, WC (2012), "Några resultat på incidensfärgning, stjärnarboricitet och dominansnummer" ( PDF) , Australasian Journal of Combinitorics , vol. 54, s. 107–114 .
Wu, J. (2009), "Some results on the incidence coloring number of a graph" , Discrete Mathematics , vol. 309, s. 3866–3870 .
Li, X; Tu, J. (2008), "NP-fullständighet av 4-incidens färgbarhet av semi-kubiska grafer", Discrete Mathematics , vol. 308, s. 1334–1340 .
Pai, KJ; Chang, JM; Wu, RY (2014), "Incidensfärgning på hyperkuber" , Theoretical Computer Science , vol. 557, s. 59–65 .
Pai, KJ; Chang, JM; Wu, RY (2014), "On the Incident Coloring Number of Folded hypercubes" , Proceedings of the 18th International Computer Science and Engineering Conference (ICSEC 2014), 30 juli - 1 augusti, Khon Kaen, Thailand, s. 7–11 .
Sopena, É.; Wu, J ( 2013), "The incidence chromatic number of toroidal grids", Discussiones Mathematicae Graph Theory , 33 (2): 315–327, arXiv : 0907.3801 , doi : 10.7151 / 5.1663 dmgt.12C1
Andres, SD (2009). "Erratum to: The incidence game chromatic number". Diskret tillämpad matematik . 158 (6): 728. doi : 10.1016/j.dam.2009.11.017 .
Charpentier, C.; Sopena, É. (2015), "The incidence game chromatic number of (a,d)- decomposable graphs" , Journal of Discrete Algorithms , vol. 31, s. 14–25 .
Wu, J.; Zhu, X. (2008), "The 6-relaxed game chromatic number of outerplanar graphs", Discrete Mathematics , 308 (24): 5974–5980, doi : 10.1016/j.disc.2007.11.015 .
Meng, X.; Guo, J.; Su, B. (2012), "Incidensfärgning av pseudo Halin-grafer" , Discrete Mathematics , 312 (22): 3276–3282, doi : 10.1016/j.disc.2012.07.024 .
Andres, SD (2009), "Lightness of digraphs in surfaces and directioned game chromatic number" , Discrete Mathematics , vol. 309, s. 3564–3579 .
Li, X; Tu, J. (2008), "NP-completeness of 4-incidence colorability of semi-cubic graphs" , Discrete Mathematics , 308 (7): 1334–1340, arXiv : math/0607071 , doi : 10.1016/j.disc. 2007.03.076 , S2CID 59464 .
Zhu, X. (1999), "The Game Coloring Number of Planar Graphs", Journal of Combinatorial Theory, Series B , 75 (2): 245–258, doi : 10.1006/jctb.1998.1878 .
Liu, X.; Li, Y. (2005), "The incidence chromatic number of some graph", International Journal of Mathematics and Mathematical Sciences , 1 (5): 803–813, doi : 10.1155/IJMMS.2005.803 .
Dong, GX; Liu, XF (2014), "Incidence Coloring Number of Some Join Graphs" , Applied Mechanics and Materials , 602–605: 3185–3188, doi : 10.4028 /www.scientific.net/AMM.602-605.3185 92 6CID 92 6CID .

Se även