A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

被引：9

作者：

Carbonero, Alvaro ^{[1
]}

Hompe, Patrick ^{[1
]}

Moore, Benjamin ^{[2
]}

Spirkl, Sophie ^{[1
]}

机构：

[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON, Canada

[2] Charles Univ Prague, Inst Comp Sci, Prague, Czech Republic

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2023年 / 158卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Directed graph; chi-Boundedness; Induced subgraph;

D O I：

10.1016/j.jctb.2022.09.001

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that for every n, there is a graph G with chi(G) >= n and omega (G) <= 3 such that every induced subgraph H of G with omega (H) <= 2 satisfies chi(H) <= 4. This disproves a well-known conjecture. Our construction is a digraph with bounded clique number, large dichromatic number, and no induced directed cycles of odd length at least 5. (C) 2022 Elsevier Inc. All rights reserved.

引用

页码：63 / 69

页数：7

共 12 条

[1] Chordal directed graphs are not directed χ-bounded [J].

Aboulker, Pierre ;

Bousquet, Nicolas ;

de Verclos, Remi .

ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (02)

[2]

Carbonero A, 2022, Arxiv, DOI arXiv:2203.15575

[3]

Erdos P., 1979, P 9 MAN C NUM MATH C, P3

[4]

Gyarfas A., 1987, P INT C COMBINATORIA, V19, P413

[5] COLORFUL INDUCED SUBGRAPHS [J].

KIERSTEAD, HA ;

TROTTER, WT .

DISCRETE MATHEMATICS, 1992, 101 (1-3) :165-169

[6]

Nesetril Jaroslav, 1979, TEORIE GRAFU, V1

[7] THE DICHROMATIC NUMBER OF A DIGRAPH [J].

NEUMANNLARA, V .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1982, 33 (03) :265-270

[8] CHROMATIC NUMBER OF SUBGRAPHS OF A GIVEN GRAPH [J].

RODL, V .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1977, 64 (02) :370-371

[9] A survey of χ-boundedness [J].

Scott, Alex ;

Seymour, Paul .

JOURNAL OF GRAPH THEORY, 2020, 95 (03) :473-504

[10] Induced subgraphs of graphs with large chromatic number. I. Odd holes [J].

Scott, Alex ;

Seymour, Paul .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 :68-84

← 1 2 →