Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph

Pokaži ostale verzije (1)

We prove that for every path H, and every integer d, there is a polynomial f such that every graph G with chromatic number greater than f(t) either contains H as an induced subgraph, or contains as a subgraph the complete d-partite graph with parts of cardinality t. For t = 1 and general d this is a...

Bibliografski detalji
Glavni autori:	Nguyen, T, Scott, AD, Seymour, P
Format:	Journal article
Jezik:	English
Izdano:	Wiley 2024

Slični predmeti

Polynomial bounds for chromatic number VIII. Excluding a path and a complete multipartite graph
od: Nguyen, T, i dr.
Izdano: (2024)

Polynomial bounds for chromatic number. V. Excluding a tree of radius two and a complete multipartite graph
od: Scott, A, i dr.
Izdano: (2023)

Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path
od: Scott, A, i dr.
Izdano: (2023)

Polynomial bounds for chromatic number II: excluding a star-forest
od: Scott, A, i dr.
Izdano: (2022)

Polynomial bounds for chromatic number III: excluding a double star
od: Scott, A, i dr.
Izdano: (2022)

Polynomial bounds for chromatic number. I: excluding a biclique and an induced tree
od: Scott, A, i dr.
Izdano: (2022)

Polynomial bounds for chromatic number VI. Adding a four-vertex path
od: Chudnovsky, M, i dr.
Izdano: (2023)

On the Delta(d)–chromatic number of a complete balanced multipartite graph
od: AP Burger, i dr.
Izdano: (2007-06-01)

Polynomial bounds for chromatic number VII. Disjoint holes
od: Chudnovsky, M, i dr.
Izdano: (2023)

On the chromaticity of complete multipartite graphs with certain edges added
od: Lau, G. C., i dr.
Izdano: (2008)

Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
od: Chudnovsky, M, i dr.
Izdano: (2019)

Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
od: Chudnovsky, M, i dr.
Izdano: (2019)

Pure pairs. VIII. Excluding a sparse graph
od: Scott, A, i dr.
Izdano: (2024)

Bell Numbers of Complete Multipartite Graphs
od: Julian Allagan, i dr.
Izdano: (2016-08-01)

Induced subgraphs of graphs with large chromatic number IX: rainbow paths
od: Scott, A, i dr.
Izdano: (2017)

An improved bound on the chromatic number of the Pancake graphs
od: Leen Droogendijk, i dr.
Izdano: (2024-01-01)

An upper bound for the chromatic number of line graphs
od: Andrew D. King, i dr.
Izdano: (2005-01-01)

Ultrametrics and Complete Multipartite Graphs
od: Viktoriia Viktorivna Bilet, i dr.
Izdano: (2022-06-01)

An upper bound on the chromatic number of 2-planar graphs
od: Dmitri Karpov
Izdano: (2023-01-01)

Chromatic polynomials of signed graphs
od: Utomo, Charissa Irene
Izdano: (2023)

Generalized Ramsey numbers for paths in 2-chromatic graphs
od: R. Meenakshi, i dr.
Izdano: (1986-01-01)

On the Locating Chromatic Number of Barbell Shadow Path Graph
od: A. Asmiati, i dr.
Izdano: (2021-12-01)

Induced subgraphs of graphs with large chromatic number. XI. orientations
od: Chudnovsky, M, i dr.
Izdano: (2018)

Seidel energy of complete multipartite graphs
od: Oboudi Mohammad Reza
Izdano: (2021-04-01)

A strict upper bound for size multipartite Ramsey numbers of paths versus stars
od: Chula Jayawardene, i dr.
Izdano: (2017-08-01)

Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes
od: Scott, A, i dr.
Izdano: (2018)

Induced subgraphs of graphs with large chromatic number. VI. Banana trees
od: Scott, A, i dr.
Izdano: (2020)

Induced subgraphs of graphs with large chromatic number. XIII. New brooms
od: Scott, A, i dr.
Izdano: (2019)

Induced subgraphs of graphs with large chromatic number. I. Odd holes
od: Scott, A, i dr.
Izdano: (2015)

Excluding pairs of graphs
od: Chudnovsky, M, i dr.
Izdano: (2014)

Bivariate Chromatic Polynomials of Mixed Graphs
od: Matthias Beck, i dr.
Izdano: (2023-11-01)

Chromatic Polynomials of Signed Book Graphs
od: Deepak Sehrawat, i dr.
Izdano: (2022-03-01)

Note on chromatic polynomials of the threshold graphs
od: Noureddine Chikh, i dr.
Izdano: (2019-10-01)

Induced subgraphs of graphs with large chromatic number. III. Long holes
od: Chudnovsky, M, i dr.
Izdano: (2016)

Induced subgraphs of graphs with large chromatic number. XII. Distant stars
od: Chudnovsky, M, i dr.
Izdano: (2019)

Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
od: Chudnovsky, M, i dr.
Izdano: (2021)

Induced subgraphs of graphs with large chromatic number. VII. Gyárfás' complementation conjecture
od: Scott, A, i dr.
Izdano: (2020)

Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
od: Scott, A, i dr.
Izdano: (2019)

An exact value for the path-chromatic index of a complete graph
od: Frank Harary, i dr.
Izdano: (1989-10-01)

Empirical studies of efficiency of some bounds on the chromatic number of random graphs /
od: Ghazali Sulong, 1958-, i dr.