On the Second Order Chromatic Number and Maximal Criticality of a Graph

Abstract

Given positive integers $p$ and $q$, a $(p,q)$-colouring of a graph $G$ is a mapping $\theta :V(G)\to \{1,2,\dots ,q\}$ such that $\theta (u)\ne \theta (v)$ for all distinct vertices $u,v$ in $G$ whose distance $d(u,v)\le p$. The $p$th order chromatic number ${\chi }^{(p)}(G)$ of $G$ is the minimum value of $q$ such that $G$ admits a $(p,q)$-colouring. $G$ is said to be $(p,q)$-maximally critical if ${\chi }^{(p)}(G)=q$ and ${\chi }^{(p)}(G+e)>q$ for each edge $e$ not in $G$.
In this paper, we study the structure of $(2,q)$-maximally critical graphs. Some necessary or sufficient conditions for a graph to be $(2,q)$-maximally critical are obtained. Let $G$ be a $(2,q)$-maximally critical graph with colour classes $V_1,V_2,\dots ,V_q$. We show that if $|V_1|=|V_2|=\cdots =|V_k|=1$ and $|V_{k+1}|=\cdots =|V_q|=h\ge 1$ for some $k$, where $1\le k\le q-1$, then $h\le h^{\ast }$, where

$$h^{\ast }=max\{k,min\{q–1,2(q–1–k)\}\}.$$

Furthermore, for each $h$ with $1\le h\le h^{\ast }$, we are able to construct a $(2,q)$-maximally critical connected graph with colour classes $V_1,V_2,\dots ,V_q$ such that $|V_1|=|V_2|=\cdots =|V_k|=1$ and $|V_{k+1}|=\cdots =|V_q|=h$.