Simpler multicoloring of triangle-free hexagonal graphs

Sau Walls, Ignasi; Šparl, Petra; Žerovnik, Janez

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Simpler multicoloring of triangle-free hexagonal graphs
Authors:	ID Sau Walls, Ignasi (Author) ID Šparl, Petra (Author) ID Žerovnik, Janez (Author)
Files:	http://dx.doi.org/10.1016/j.disc.2011.07.031
Language:	English
Work type:	Not categorized
Typology:	1.08 - Published Scientific Conference Contribution
Organization:	FOV - Faculty of Organizational Sciences in Kranj
Abstract:	Preslikavo $f colon V(G)to 2^{{1,.,n}}$ , za katero velja $\|f(v)\| ge p(v)$ za vsako točko $v in V(G)$ in $f(v) cap f(u) = emptyset$ za poljubni sosedi $u$ in $v$ grafa $G$ , imenujemo dobro $n-[p]$ barvanje grafa $G$ . Najmanjše naravno število, za katero obstaja dobro $n-[p]$ barvanje grafa $G$ , $chi_p(G)$ , imenujemo uteženo kromatično število grafa $G$ . Iskanje uteženega kromatičnega števila za inducirane podgrafe trikotniške mreže (imenovane heksagonalni grafi) ima aplikacije v celičnih mrežah. Uteženo kromatično število grafa $G$ , $omega_p(G)$ , je enako maksimalni uteži klike grafa $G$ , kjer utež klike predstavlja vsoto uteži njenih točk. McDiarmid in Reed (2000) sta postavila domnevo, da za poljuben heksagonalen graf brez trikotnikov velja $chi_p(G) le (9/8)omega_p(G) + C$ . V članku je podan algoritem, ki poda dobro $7-[3]$ barvanje poljubnega heksagonalnega grafa brez trikotnikov, ki aplicira neenakost $chi_p(G) le (7/6)omega_p(G) + C$ . Naš rezultat podaja krajšo alternativo induktivnega dokaza Haveta (2001) in izboljša kratek dokaz Sudepa in Vishwanathana (2005), ki sta dokazala obstoj $14-[6]$ barvanja. (Omeniti je potrebno, da v sklopu našega dokaza uporabimo izrek o štirih barvah.) Vsi koraki algoritma so linearni glede na $\|V(G)\|$ , razen 4-barvanje ravninskega grafa. Novi pristop lahko v prihodnje pripomore k dokazovanju domneve McDiarmida in Reeda (2000).
Keywords:	matematika, teorija grafov, aproksimacijski algoritem, barvanje grafov, dodeljevanje frekvenc, celične mreže, mathematics, graph algorithm, graph theory, approximation algorithm, graph coloring, frequency planning, cellular networks
Year of publishing:	2012
Number of pages:	Str. 181-187
Numbering:	Vol. 312, iss. 1
PID:	20.500.12556/DKUM-51432
UDC:	519.17
ISSN on article:	0012-365X
COBISS.SI-ID:	6917907
NUK URN:	URN:SI:UM:DK:IOFJJWSU
Publication date in DKUM:	10.07.2015
Views:	1351
Downloads:	89
Metadata:
Categories:	Misc.
:	SAU WALLS, Ignasi, ŠPARL, Petra and ŽEROVNIK, Janez, 2012, Simpler multicoloring of triangle-free hexagonal graphs. In : Algebraic graph theory [online]. Published Scientific Conference Contribution. 2012. p. 181–187. [Accessed 21 April 2025]. Retrieved from: http://dx.doi.org/10.1016/j.disc.2011.07.031 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Searching for similar works... Please wait....

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a proceedings

Title:	Algebraic graph theory
COBISS.SI-ID:	16067161

Record is a part of a journal

Title:	Discrete mathematics
Shortened title:	Discrete math.
Publisher:	North-Holland
ISSN:	0012-365X
COBISS.SI-ID:	1118479

Secondary language

Language:	English
Title:	Enostavnejše večbarvanje heksagonalnih grafov brez trikotnikov
Abstract:	Given a graph $G$ and a demand function $p colon V(G)to mathbb{N}$ , a proper $n-[p]$ coloring is a mapping $f colon V(G)to 2^{{1,.,n}}$ such that $\|f(v)\| ge p(v)$ for every vertex $v in V(G)$ and $f(v) cap f(u) = emptyset$ for any two adjacent vertices $u$ and $v$ . The least integer $n$ for which a proper $n-[p]$ coloring exists, $chi_p(G)$ , is called multichromatic number of $G$ . Finding multichromatic number of induced subgraphs of the triangular lattice (called hexagonal graphs) has applications in cellular networks. Weighted clique number of a graph $G$ , $omega_p(G)$ , is the maximum weight of a clique in $G$ , where the weight of a clique is the total demand of its vertices. McDiarmid and Reed (2000) conjectured that $chi_p(G) le (9/8)omega_p(G)+C$ for triangle-free hexagonal graphs, where $C$ is some absolute constant. In this article, we provide an algorithm to find a $7-[3]$ coloring of triangle-free hexagonal graphs (that is, when $p(v) = 3$ for all $v in V(G)$ ), which implies that $chi_p(G) le (7/6)omega_p(G) + C$ . Our result constitutes a shorter alternative to the inductive proof of Havet (2001) and improves the short proof of Sudeep and Vishwanathan (2005), who proved the existence of a $14-[6]$ coloring. (It has to be noted, however, that our proof makes use of the 4-color theorem.) All steps of our algorithm take time linear in $\|V(G)\|$ , except for the 4-coloring of an auxiliary planar graph. The new techniques may shed some light on the conjecture of McDiarmid and Reed (2000).

Comments

Leave comment

You must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back