Skip to content
Preprint

2-Distance Coloring of 4-Irregular Planar Graphs

Aug 2026 · 0 citations
Mathematics

Abstract

A $k$-irregular graph is a graph with maximum degree $k$ such that vertices of degree $k$ are not adjacent. A $2$-distance $k$-coloring of a graph is a coloring of the vertices using $k$ colors in which any two vertices at distance at most $2$ receive distinct colors. The $2$-distance chromatic number of $G$, denoted by $\chi_{2}(G)$, is the minimum integer $k$ such that $G$ admits a $2$-distance $k$-coloring. Zhu \cite{zhu} proved that $\chi_2(G)\leq 13$ for planar graphs with maximum degree at most $4$. We prove that for a 4-irregular planar graph $G$, we have $\chi_2(G) \leq 10$.

View source

Similar papers

Preprint Sep 2026

B-coloring of $K_{2,t}$-free planar graphs

A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle receives four distinct colors; let $q_B(G)$ be the minimum number of colors in such a coloring. Every graph of maximum degree $\Delta$ is $K_{2,\Delta+1}$-free; hence the known $2\Delta$ bound for planar graphs with $\Delta\ge38$ (Kong et al...

Zheng Jiang · 1 citation
Preprint Aug 2026

List coloring $C_3$-free planar graphs with a sparse matching of restricted lists

A graph $G$ is $k$-choosable if it has a proper coloring for every $k$-list assignment. While every $C_3$-free planar graph is $4$-choosable, some of them are not $3$-choosable, as constructed by Voigt. Hu and Zhu conjectured that if $G$ is a $C_3$-free planar graph and $X \subseteq V(G)$ induces a bipartite subgraph,...

S. Hartke, Yu-Pei Li, Joseph Pappe et al. · 0 citations
Preprint Sep 2026

Strong edge coloring of graphs with maximum degree $6$

Let $G$ be a graph. Under a strong edge coloring of $G$, every color class is an induced matching. The strong chromatic index of $G$, denoted by $\chi'_s(G)$, is the smallest integer $k$ such that $G$ admits a strong edge coloring with $k$ colors. Denote by $\Delta(G)$ the maximum degree of $G$. In this paper, we prove...

Run-Ze Wang · 0 citations
Preprint Sep 2026

A stronger upper bound on the D-chromatic index

For a graph $G$, a proper edge coloring of $G$ is called a D-coloring if every diamond subgraph of $G$ is rainbow. Let $\chi'_D(G)$ be the D-chromatic index of $G$, which is the smallest integer $k$ such that $G$ admits a D-coloring with $k$ colors. Let $\Delta$ be the maximum degree of $G$. The only known Brooks-type...

Lin Tian, Run-Ze Wang · 0 citations
Preprint Aug 2026

Counterexamples to two conjectures on modular edge colorings of graphs

For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular...

Chun-Qiang Guo, Baoyindureng Wu · 0 citations
Preprint Sep 2026

Counting edge-colorings of a complete graph avoiding a rainbow $K_4$

For $k, r, n$ natural numbers let $\rho_{r,k}(K_n)$ be the number of $r$-edge-colorings of $K_n$ that do not contain a rainbow copy of a $K_k$, that is, a copy of $K_k$ in which all edges receive different colors. When $k=3$, the quantity $\rho_{r,3}(K_n)$ represents the number of Gallai Colorings. It was proved by Bal...

F. Benevides, Josefran de O. Bastos · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.