Forbidden Subgraphs Generating Almost All Claw-Free Graphs with High Connectivity

被引：0

作者：

Furuya, Michitaka ^{[1
]}

Yokota, Maho ^{[2
]}

机构：

[1] Kitasato Univ, Coll Liberal Arts & Sci, Sagamihara, Kanagawa 2520373, Japan

[2] Tokyo Univ Sci, Dept Appl Math, Tokyo 1628601, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2019年 / E102A卷 / 09期

关键词：

claw-free graph; forbidden subgraph; Matthews-Sumner conjecture; HAMILTONICITY; EQUIVALENCE;

D O I：

10.1587/transfun.E102.A.987

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

For a family H of connected graphs and an integer k >= 1, let G(k)(H) denote the family of k-connected graphs which contain no element of H as an induced subgraph. Let H+ be the family of those connected graphs of order 5 which contain K-1,K-3 as an induced subgraph. In this paper, for each integer k >= 1, we characterize the families H subset of H+ such that the symmetric difference of G(k)(K-1,K-3) and Gk (H) is finite.

引用

页码：987 / 993

页数：7

共 21 条

[1]

[Anonymous], J GRAPH THEOR

[2]

[Anonymous], ADV APPL DISCRETE MA

[3] How Many Conjectures Can You Stand? A Survey [J].

Broersma, H. J. ;

Ryjacek, Z. ;

Vrana, P. .

GRAPHS AND COMBINATORICS, 2012, 28 (01) :57-75

[4] Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks [J].

Broersma, Hajo ;

Fijavz, Gasper ;

Kaiser, Tomas ;

Kuzel, Roman ;

Ryjacek, Zdenek ;

Vrana, Petr .

DISCRETE MATHEMATICS, 2008, 308 (24) :6064-6077

[5] On factors of 4-connected claw-free graphs [J].

Broersma, HJ ;

Kriesell, M ;

Ryjácek, Z .

JOURNAL OF GRAPH THEORY, 2001, 37 (02) :125-136

[6] Equivalence of Jackson's and Thomassen's conjectures [J].

Cada, Roman ;

Chiba, Shuya ;

Ozeki, Kenta ;

Vrana, Petr ;

Yoshimoto, Kiyoshi .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 114 :124-147

[7]

Diestel R., 2010, Graduate Text in Mathematics, V4th

[8] A note about the dominating circuit conjecture [J].

Fleischner, H ;

Kochol, M .

DISCRETE MATHEMATICS, 2002, 259 (1-3) :307-309

[9] Forbidden Subgraphs for Hamiltonicity of 3-Connected Claw-Free Graphs [J].

Fujisawa, Jun .

JOURNAL OF GRAPH THEORY, 2013, 73 (02) :146-160

[10] Forbidden induced subgraphs for star-free graphs [J].

Fujisawa, Jun ;

Ota, Katsuhiro ;

Ozeki, Kenta ;

Sueiro, Gabriel .

DISCRETE MATHEMATICS, 2011, 311 (21) :2475-2484

← 1 2 3 →