View in EDS

On the Span of ℓ Distance Coloring of Infinite Hexagonal Grid.

Saved in:
Bibliographic Details
Title: On the Span of ℓ Distance Coloring of Infinite Hexagonal Grid.
Authors: Koley, Subhasis1 (AUTHOR) subhasis.koley2@gmail.com, Ghosh, Sasthi C.2 (AUTHOR) sasthi@isical.ac.in
Source: International Journal of Foundations of Computer Science. Nov2024, Vol. 35 Issue 7, p791-813. 23p.
Subjects: Graph coloring, Computer science conferences, Assignment problems (Programming), Graph theory, Regular graphs, Integers
Abstract: For a graph G (V , E) and ℓ ∈ ℕ , an ℓ distance coloring is a coloring f : V → { 1 , 2 , ... , t } of V with t colors such that ∀ u , v ∈ V , u ≠ v , f (u) ≠ f (v) when d (u , v) ≤ ℓ. Here d (u , v) is the distance between u and v and is equal to the minimum number of edges that connect u and v in G. The span of ℓ distance coloring of G , χ ℓ (G) , is the minimum t among all ℓ distance coloring of G. A class of channel assignment problem in cellular network can be formulated as a distance graph coloring problem in regular grid graphs. The cellular network is often modelled as an infinite hexagonal grid H , and hence determining χ ℓ (H) has relevance from practical point of view. Jacko and Jendrol [Discussiones Mathematicae Graph Theory, 2005] determined the exact value of χ ℓ (H) for any odd ℓ and for even ℓ ≥ 8 , it is conjectured that χ ℓ (H) = 3 8 (ℓ + 4 3) 2 where [ x ] is an integer, x ∈ ℝ and x − 1 2 < [ x ] ≤ x + 1 2 . For ℓ = 8 , the conjecture has been proved by Ghosh and Koley [ 2 2 nd Italian Conference on Theoretical Computer Science, 2021]. In this paper, we prove the conjecture for any even ℓ ≥ 1 0. [ABSTRACT FROM AUTHOR]
Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 180496566
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the Span of ℓ Distance Coloring of Infinite Hexagonal Grid.
– Name: Author
  Label: Authors
  Group: Au
  Data: &lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Koley%2C+Subhasis%22&quot;&gt;Koley, Subhasis&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; subhasis.koley2@gmail.com&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Ghosh%2C+Sasthi+C%2E%22&quot;&gt;Ghosh, Sasthi C.&lt;/searchLink&gt;&lt;relatesTo&gt;2&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; sasthi@isical.ac.in&lt;/i&gt;
– Name: TitleSource
  Label: Source
  Group: Src
  Data: &lt;searchLink fieldCode=&quot;JN&quot; term=&quot;%22International+Journal+of+Foundations+of+Computer+Science%22&quot;&gt;International Journal of Foundations of Computer Science&lt;/searchLink&gt;. Nov2024, Vol. 35 Issue 7, p791-813. 23p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: &lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Graph+coloring%22&quot;&gt;Graph coloring&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Computer+science+conferences%22&quot;&gt;Computer science conferences&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Assignment+problems+%28Programming%29%22&quot;&gt;Assignment problems (Programming)&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Graph+theory%22&quot;&gt;Graph theory&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Regular+graphs%22&quot;&gt;Regular graphs&lt;/searchLink&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Integers%22&quot;&gt;Integers&lt;/searchLink&gt;
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: For a graph G (V , E) and ℓ ∈ ℕ , an ℓ distance coloring is a coloring f : V → { 1 , 2 , ... , t } of V with t colors such that ∀ u , v ∈ V , u ≠ v , f (u) ≠ f (v) when d (u , v) ≤ ℓ. Here d (u , v) is the distance between u and v and is equal to the minimum number of edges that connect u and v in G. The span of ℓ distance coloring of G , χ ℓ (G) , is the minimum t among all ℓ distance coloring of G. A class of channel assignment problem in cellular network can be formulated as a distance graph coloring problem in regular grid graphs. The cellular network is often modelled as an infinite hexagonal grid H , and hence determining χ ℓ (H) has relevance from practical point of view. Jacko and Jendrol [Discussiones Mathematicae Graph Theory, 2005] determined the exact value of χ ℓ (H) for any odd ℓ and for even ℓ ≥ 8 , it is conjectured that χ ℓ (H) = 3 8 (ℓ + 4 3) 2 where [ x ] is an integer, x ∈ ℝ and x − 1 2 &lt; [ x ] ≤ x + 1 2 . For ℓ = 8 , the conjecture has been proved by Ghosh and Koley [ 2 2 nd Italian Conference on Theoretical Computer Science, 2021]. In this paper, we prove the conjecture for any even ℓ ≥ 1 0. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: &lt;i&gt;Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder&#39;s express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.&lt;/i&gt; (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=180496566
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1142/S012905412350020X
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 23
        StartPage: 791
    Subjects:
      – SubjectFull: Graph coloring
        Type: general
      – SubjectFull: Computer science conferences
        Type: general
      – SubjectFull: Assignment problems (Programming)
        Type: general
      – SubjectFull: Graph theory
        Type: general
      – SubjectFull: Regular graphs
        Type: general
      – SubjectFull: Integers
        Type: general
    Titles:
      – TitleFull: On the Span of ℓ Distance Coloring of Infinite Hexagonal Grid.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Koley, Subhasis
      – PersonEntity:
          Name:
            NameFull: Ghosh, Sasthi C.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: Nov2024
              Type: published
              Y: 2024
          Identifiers:
            – Type: issn-print
              Value: 01290541
          Numbering:
            – Type: volume
              Value: 35
            – Type: issue
              Value: 7
          Titles:
            – TitleFull: International Journal of Foundations of Computer Science
              Type: main
ResultId 1