Source author record

Hui Lei

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Weak-odd chromatic index of special digraph classes

Give a digraph $D=(V(D),A(D))$ , let $\partial^+_D(v)=\{vw|w\in N^+_D(v)\}$ and $\partial^-_D(v)=\{uv|u\in N^-_D(v)\}$ be semi-cuts of $v$ . A mapping $φ:A(D)\rightarrow [k]$ is called a weak-odd $k$ -edge coloring of $D$ if it satisfies the condition: for each $v\in V(D)$ , there is at least one color with an odd number of occurrences on each non-empty semi-cut of $v$ . We call the minimum integer $k$ the weak-odd chromatic index of $D$ . When limit to 2 colors, use $def(D)$ to denote the defect of $D$ , the minimum number of vertices in $D$ at which the above condition is not satisfied. In this paper, we give a descriptive characterization about the weak-odd chromatic index and the defect of semicomplete digraphs and extended tournaments, which generalize results of tournaments to broader classes. And we initiated the study of weak-odd edge covering on digraphs.

preprint2020arXiv

A survey on star edge-coloring of graphs

The star chromatic index of a multigraph $G$ , denoted $χ'_{st}(G)$ , is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bicolored. We survey the results of determining the star chromatic index, present the interesting proofs and techniques, and collect many open problems and conjectures.

preprint2020arXiv

k-Ary spanning trees contained in tournaments

A rooted tree is called a $k$ -ary tree, if all non-leaf vertices have exactly $k$ children, except possibly one non-leaf vertex has at most $k-1$ children. Denote by $h(k)$ the minimum integer such that every tournament of order at least $h(k)$ contains a $k$ -ary spanning tree. It is well-known that every tournament contains a Hamiltonian path, which implies that $h(1)=1$ . Lu et al. [J. Graph Theory {\bf 30}(1999) 167--176] proved the existence of $h(k)$ , and showed that $h(2)=4$ and $h(3)=8$ . The exact values of $h(k)$ remain unknown for $k\geq 4$ . A result of Erdős on the domination number of tournaments implies $h(k)=Ω(k\log k)$ . In this paper, we prove that $h(4)=10$ and $h(5)\geq13$ .

preprint2020arXiv

Some extremal results on the chromatic-stability index

The $χ$ -stability index ${\rm es}_χ(G)$ of a graph $G$ is the minimum number of its edges whose removal results in a graph with the chromatic number smaller than that of $G$ . In this paper three open problems from [European J.\ Combin.\ 84 (2020) 103042] are considered. Examples are constructed which demonstrate that a known characterization of $k$ -regular ( $k\le 5$ ) graphs $G$ with ${\rm es}_χ(G) = 1$ does not extend to $k\ge 6$ . Graphs $G$ with $χ(G)=3$ for which ${\rm es}_χ(G)+{\rm es}_χ(\overline{G}) = 2$ holds are characterized. Necessary conditions on graphs $G$ which attain a known upper bound on ${\rm es}_χ(G)$ in terms of the order and the chromatic number of $G$ are derived. The conditions are proved to be sufficient when $n\equiv 2 \pmod 3$ and $χ(G)=3$ .

preprint2017arXiv

Star 5-edge-colorings of subcubic multigraphs

The star chromatic index of a multigraph $G$ , denoted $χ'_{s}(G)$ , is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bi-colored. A multigraph $G$ is star $k$ -edge-colorable if $χ'_{s}(G)\le k$ . Dvořák, Mohar and Šámal [Star chromatic index, J Graph Theory 72 (2013), 313--326] proved that every subcubic multigraph is star $7$ -edge-colorable, and conjectured that every subcubic multigraph should be star $6$ -edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than $7/3$ is star list- $5$ -edge-colorable. It is known that a graph with maximum average degree $14/5$ is not necessarily star $5$ -edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than $12/5$ is star $5$ -edge-colorable.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Hui Lei

Research overview

Is this your work?

5 publications

Weak-odd chromatic index of special digraph classes

A survey on star edge-coloring of graphs

k-Ary spanning trees contained in tournaments

Some extremal results on the chromatic-stability index

Star 5-edge-colorings of subcubic multigraphs

See the researcher in context

Building this map preview