Two coloring problems on matrix graphs

DOI10.1142/S1793830916500531MaRDI QIDQ2821120zbMATH OpenFDO

Authors Zhe Han, Mei Lu

Publication date 16 September 2016

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07239

zbMATH Keywords

vertex coloringcoloring problemcoding theoryGabidulin codes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Linear codes (general theory) (94B05) Bounds on codes (94B65)

Abstract: In this paper, we propose a new family of graphs, matrix graphs, whose vertex set $mathbb{F}_q^{Nimesn}$ is the set of all $Nimesn$ matrices over a finite field $mathbb{F}_q$ for any positive integers $N$ and $n$. And any two matrices share an edge if the rank of their difference is $1$. Next, we give some basic properties of such graphs and also consider two coloring problems on them. Let $chi{\text{'}}_d(Nimesn,q)$ (resp. $ch{i}_d(Nimesn,q)$) denote the minimum number of colors necessary to color the above matrix graph so that no two vertices that are at a distance at most $d$ (resp. exactly $d$) get the same color. These two problems were proposed in the study of scalability of optical networks. In this paper, we determine the exact value of $chi{\text{'}}_d(Nimesn,q)$ and give some upper and lower bounds on $ch{i}_d(Nimesn,q)$.

Recommendations

• Orthogonal representations over finite fields and the chromatic number of graphs
• New results on two hypercube coloring problems
• Perfect colorings of the infinite rectangular grid
• New bounds on a hypercube coloring problem.
• Chromatic number of classes of matrices of zeros and ones

Cites work

• scientific article; zbMATH DE number 5139444 (Why is no real title available?)
• A coloring problem on the \(n\)-cube
• A note on linearized polynomials and the dimension of their kernels
• BCH codes and distance multi- or fractional colorings in hypercubes asymptotically
• Bilinear forms over a finite field, with applications to coding theory
• Coding for Errors and Erasures in Random Network Coding
• Equidistant codes in the Grassmannian
• Equidistant rank metric codes: construction and properties
• Generalized Hypercube and Hyperbus Structures for a Computer Network
• Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network
• New bounds on a hypercube coloring problem.
• New results on two hypercube coloring problems
• On the distance chromatic number of Hamming graphs
• Theory of codes with maximum rank distance

Cited in

(1)

• On two coloring problems in mixed graphs

This page was built for publication: Two coloring problems on matrix graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2821120)