☆ 4.2 Article

Odd Induced Subgraphs in Planar Graphs with Large Girth

GRAPHS AND COMBINATORICS (2022)

VERTEX PARTITIONING OF GRAPHS INTO ODD

Arman Aashtab et al.

Summary: In this paper, we investigate the partition problem of connected graphs with even order, proving that for a connected subcubic graph or a connected planar graph with even order, the minimum number of odd induced subgraphs in the partition does not exceed 4. We also demonstrate that for a tree of even order, the minimum number of odd induced subgraphs does not exceed 2, and for a unicyclic graph of even order, it does not exceed 3. Additionally, we prove that if the graph is claw-free, the vertex set can be partitioned into at most |Δ(G)|-1 induced forests and possibly one independent set. Furthermore, we show that the vertex set of the line graph of a tree can be partitioned into at most two odd induced subgraphs and possibly one independent set.

DISCUSSIONES MATHEMATICAE GRAPH THEORY (2023)

添加到收藏夹

Article Computer Science, Information Systems

Full friendly index sets of mCn

Yurong Ji et al.

Summary: This paper investigates the full friendly index set of a family of graphs, exploring the relationship between friendly vertex labeling and edge labeling functions.

FRONTIERS OF COMPUTER SCIENCE (2022)

添加到收藏夹

Article Mathematics

Every graph contains a linearly sized induced subgraph with all degrees odd

Asaf Ferber et al.

Summary: This article proves an old and well-known conjecture in graph theory, stating that every graph with no isolated vertices contains an induced subgraph of size at least n/10000 with all degrees odd.

ADVANCES IN MATHEMATICS (2022)

添加到收藏夹

Article Computer Science, Information Systems

VColor*: a practical approach for coloring large graphs

Yun Peng et al.

Summary: Graph coloring has broad applications in various fields, and our VColor and VColor* approaches address efficiency challenges in graph coloring. VColor* demonstrates superior efficiency compared to VColor in experimental evaluations.

FRONTIERS OF COMPUTER SCIENCE (2021)

添加到收藏夹

Article Mathematics, Applied