Vertex-critical graphs far from edge-criticality

被引：0

作者：

Martinsson, Anders ^{[1
]}

Steiner, Raphael ^{[1
]}

机构：

[1] Swiss Fed Inst Technol, Inst Theoret Comp Sci, Dept Comp Sci, Zurich, Switzerland

来源：

COMBINATORICS PROBABILITY AND COMPUTING | 2025年 / 34卷 / 01期

关键词：

Chromatic number; colour-critical graphs; hypergraphs; probabilistic method;

D O I：

10.1017/S0963548324000324

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let $r$ be any positive integer. We prove that for every sufficiently large $k$ there exists a $k$ -chromatic vertex-critical graph $G$ such that $\chi (G-R)=k$ for every set $R \subseteq E(G)$ with $|R|\le r$ . This partially solves a problem posed by Erd & odblac;s in 1985, who asked whether the above statement holds for $k \ge 4$ .

引用

页码：151 / 157

页数：7

共 12 条

[1] A VERTEX CRITICAL GRAPH WITHOUT CRITICAL EDGES [J].

BROWN, JI .

DISCRETE MATHEMATICS, 1992, 102 (01) :99-101

[2]

Chung F., 2012, ONLINE DATABASE ERDO

[3]

Chung F., 1998, ERDS GRAPHS HIS LEGA

[4]

Erds P., 1985, GRAPH THEORY MEMORY, P111

[5]

Jensen T. R., 1996, PHD THESIS

[6]

Jensen Tommy R., 1995, Graph Coloring Problems

[7] Dense critical and vertex-critical graphs [J].

Jensen, TR .

DISCRETE MATHEMATICS, 2002, 258 (1-3) :63-84

[8] Factors in random graphs [J].

Johansson, Anders ;

Kahn, Jeff ;

Vu, Van .

RANDOM STRUCTURES & ALGORITHMS, 2008, 33 (01) :1-28

[9] Asymptotics for Shamir's problem [J].

Kahn, Jeff .

ADVANCES IN MATHEMATICS, 2023, 422

[10] A note on a conjecture of Dirac [J].

Lattanzio, JJ .

DISCRETE MATHEMATICS, 2002, 258 (1-3) :323-330

← 1 2 →