2018/07/20 by Aida Abiad, Abiad, Aida · 1 citation
Computer Science · Mathematics · #05C50 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #math.CO #msc:05C50 #msc:05C69
paper · pdf · doi:10.48550/arxiv.1807.07809
openalex publication_date 2018/07/20 · arxiv created 2019/01/18 · arxiv updated 2019/01/21 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
A natural generalization of a regular (or equitable) partition of a graph, which makes sense also for non-regular graphs, is the so-called weight-regular partition, which gives to each vertex u∈ V a weight that equals the corresponding entry νu of the Perron eigenvector \mathbfν. This paper contains three main results related to weight-regular partitions of a graph. The first is a characterization of weight-regular partitions in terms of double stochastic matrices. Inspired by a characterization of regular graphs by Hoffman, we also provide a new characterization of weight-regularity by using a Hoffman-like polynomial. As a corollary, we obtain Hoffman's result for regular graphs. In addition, we show an application of weight-regular partitions to study graphs that attain equality in the classical Hoffman's lower bound for the chromatic number of a graph, and we show that weight-regularity provides a condition under which Hoffman's bound can be improved.