On the Independent Coloring of Graphs with Applications to the Independence Number of Cartesian Product Graphs
Let G be a graph with V=VG. A nonempty subset S of V is called an independent set of G if no two distinct vertices in S are adjacent. The union of a class {S:S is an independent set of G} and ∅ is denoted by IG. For a graph H, a function f:V⟶IH is called an H−independent coloring of G (or simply cal...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2023-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2023/2601205 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Let G be a graph with V=VG. A nonempty subset S of V is called an independent set of G if no two distinct vertices in S are adjacent. The union of a class {S:S is an independent set of G} and ∅ is denoted by IG. For a graph H, a function f:V⟶IH is called an H−independent coloring of G (or simply called an H− coloring) if fx∩fy=∅ for any adjacent vertices x,y∈V and fV is a class of disjoint sets. Let αH,G denote the maximum cardinality of the set{∑x∈Vfx:f is an H− coloring of G}. In this paper, we obtain basic properties of an H− coloring of G and find αH,G of some families of graphs G and H. Furthermore, we apply them to determine the independence number of the Cartesian product of a complete graph Kn and a graph G and prove that αKn□G=αKn,G. |
|---|---|
| ISSN: | 2314-4785 |