First-Fit coloring of Cartesian product graphs and its defining sets
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2016
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913253514280960 |
|---|---|
| author | Zaker, Manouchehr |
| author_facet | Zaker, Manouchehr |
| contents | Let the vertices of a Cartesian product graph $G\Box H$ be ordered by an ordering $σ$. By the First-Fit coloring of $(G\Box H, σ)$ we mean the vertex coloring procedure which scans the vertices according to the ordering $σ$ and for each vertex assigns the smallest available color. Let $FF(G\Box H,σ)$ be the number of colors used in this coloring. By introducing the concept of descent we obtain a sufficient condition to determine whether $FF(G\Box H,σ)=FF(G\Box H,τ)$, where $σ$ and $τ$ are arbitrary orders. We study and obtain some bounds for $FF(G\Box H,σ)$, where $σ$ is any quasi-lexicographic ordering. The First-Fit coloring of $(G\Box H, σ)$ does not always yield an optimum coloring. A greedy defining set of $(G\Box H, σ)$ is a subset $S$ of vertices in the graph together with a suitable pre-coloring of $S$ such that by fixing the colors of $S$ the First-Fit coloring of $(G\Box H, σ)$ yields an optimum coloring. We show that the First-Fit coloring and greedy defining sets of $G\Box H$ with respect to any quasi-lexicographic ordering (including the known lexicographic order) are all the same. We obtain upper and lower bounds for the smallest cardinality of a greedy defining set in $G\Box H$, including some extremal results for Latin squares. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1606_05480 |
| institution | arXiv |
| publishDate | 2016 |
| record_format | arxiv |
| spellingShingle | First-Fit coloring of Cartesian product graphs and its defining sets Zaker, Manouchehr Combinatorics Let the vertices of a Cartesian product graph $G\Box H$ be ordered by an ordering $σ$. By the First-Fit coloring of $(G\Box H, σ)$ we mean the vertex coloring procedure which scans the vertices according to the ordering $σ$ and for each vertex assigns the smallest available color. Let $FF(G\Box H,σ)$ be the number of colors used in this coloring. By introducing the concept of descent we obtain a sufficient condition to determine whether $FF(G\Box H,σ)=FF(G\Box H,τ)$, where $σ$ and $τ$ are arbitrary orders. We study and obtain some bounds for $FF(G\Box H,σ)$, where $σ$ is any quasi-lexicographic ordering. The First-Fit coloring of $(G\Box H, σ)$ does not always yield an optimum coloring. A greedy defining set of $(G\Box H, σ)$ is a subset $S$ of vertices in the graph together with a suitable pre-coloring of $S$ such that by fixing the colors of $S$ the First-Fit coloring of $(G\Box H, σ)$ yields an optimum coloring. We show that the First-Fit coloring and greedy defining sets of $G\Box H$ with respect to any quasi-lexicographic ordering (including the known lexicographic order) are all the same. We obtain upper and lower bounds for the smallest cardinality of a greedy defining set in $G\Box H$, including some extremal results for Latin squares. |
| title | First-Fit coloring of Cartesian product graphs and its defining sets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/1606.05480 |