Graph Two-Rankings

¶ Paper Information

Title

“Graph 2-Rankings”

APA Citation

Almeter, J., Demircan, S., Kallmeyer, A., Milans, K. G., & Winslow, R. (2019). Graph 2-rankings. Graphs and Combinatorics, 35(1), 91-102.

Co-authors

Jordan Almeter, Samet Demircan, Andrew Kallmeyer, Kevin G Milans

Presented at the 2015 Miami University Annual Mathematics Conference by me, September 2015 at Miami University in Oxford, Ohio

¶ Abstract

A 2-ranking of a graph $G$ is an ordered partition of the vertices of $G$ into independent sets $V_1,…,V_t$ such that for $i<j$, the subgraph of $G$ induced by $V_i \cup V_j$ is a star forest in which each vertex in $V_i$ has degree at most 1. A 2-ranking is intermediate in strength between a star coloring and a distance-2 coloring. The 2-ranking number of $G$, denoted $\chi_2(G)$, is the minimum number of parts needed for a 2-ranking. For the d-dimensional cube $Q_d$, we prove that $\chi_2(Q_d)=d+1$. As a corollary, we improve the upper bound on the star chromatic number of products of cycles when each cycle has length divisible by 4. Let $\chi_2^\prime(G)= \chi_2(L(G)$, where $L(G)$ is the line graph of $G$; equivalently, $\chi_2^\prime(G)$ is the minimum $t$ such that there is an ordered partition of $E(G)$ into $t$ matchings $M_1,…,M_t$ such that for each $j$, the matching $M_j$ is induced in the subgraph of $G$ with edge set $M_1 \cup … \cup M_j$. We show that $\chi_2^\prime(K_{n,m})=nH_m$ when $m!$ divides $n$, where $K_{m,n}$ is the complete bipartite graph with parts of sizes $m$ and $n$, and $H_m$ is the harmonic sum $1+…+\frac{1}{m}$. We also prove that $\chi_2^\prime(G) \leq 7$ when $G$ is subcubic and show the existence of a graph $G$ with maximum degree $k$ and $\chi_2^\prime(G) \geq \Omega(k^2/\log(k))$.

¶ BibTeX info

@article{almeter2019graph,
  title={Graph 2-rankings},
  author={Almeter, Jordan and Demircan, Samet and Kallmeyer, Andrew and Milans, Kevin G and Winslow, Robert},
  journal={Graphs and Combinatorics},
  volume={35},
  number={1},
  pages={91--102},
  year={2019},
  publisher={Springer}
}